#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int main(){ long long s; long long T,n; cin>>T; while (T--){ s=1; long long sumi=1; cin>>n; for(int i=1;i<n;i++){ s+=2; sumi+=s; } cout<<sumi%10000<<endl; } return 0; }