#include<bits/stdc++.h> using namespace std; int main() { int n,t,l,s; cin>>n; for(int i=1;i<=n;i++){ cin>>t; s=0; l=1; for(int j=1;j<=t;j++){ s+=l; l+=2; } cout<<s%10000<<endl; } return 0; }