#include<iostream>
using namespace std;
#define int long long
int b;
int fast_pow(int a,int b,int mod){
int s=1;
a%=mod;
for(;b;b>>=1,a=aa%mod)if(b&1)s=sa%mod;
return s;
}
signed main(){
int n;
cin>>n;
while(n--){
cin>>b;
cout<<fast_pow(2011,b,10000)<<"\n";
}
return 0;
}
