#include<iostream> using namespace std; int main(){ int t; cin>>t; while(t--){ long long n,speed=1,sum=0; cin>>n; for(int i=0;i<n;i++){ sum+=speed; speed+=2; } cout<<sum%10000<<endl; } return 0; }