#include<bits/stdc++.h> 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; }