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