code:

#include<bits/stdc++.h>
using namespace std;
int k;
int mod(const string &n,int mod){
    int res=0;
    for (int i=0;i<n.size();i++){
        res=(res*10+(n[i]-'0'))%mod;
    }
    return res;
}
int fast(int b,int e){
	int sum=1;
	b%=10000;
	while(e>0){
		if(e&1){
			sum=(sum*b)%10000;
		}
		b=b*b%10000;
		e>>=1;
	}
	return sum;
}

int main(){
	cin>>k;
	while(k--){
		string n;
		cin>>n;
		cout<<fast(2011,mod(n,10000));
	}
	return 0;
}