#include <bits/stdc++.h>
using namespace std;
int main(){
string a1;
int a;
int k;
cin >> k;
for(int j = 0;j < k;j++){
cin >> a1;
a = 0;
for(int p = 1;p <= 3;p++){
if(a1.length() >= p){
a += (a1[a1.length()-p] - '0') * pow(10,p-1);
}
}
int b = 1;
for(int i = 0;i < a;i++){
b = b * 2011 % 10000;
}
cout << b << endl;
}		
return 0;
}

#include <bits/stdc++.h>

//仅供参考，有BUG

using namespace std;

int main(){
	string a1;
	int a;
	int k;
	cin >> k;
	for(int j = 0;j < k;j++){
		cin >> a1;
		a = 0;
		for(int p = 1;p <= 3;p++){
			if(a1.length() >= p){
				a += (a1[a1.length()-p] - '0') * pow(10,p-1);
			}
		}
		int b = 1;
		for(int i = 0;i < a;i++){
			b = b * 2011 % 10000;
		}
		cout << b;
	}		
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
	string a1;
	int a;
	int k;
	cin >> k;
	for(int j = 0;j < k;j++){
		cin >> a1;
		a = 0;
		for(int p = 1;p <= 3;p++){
			if(a1.length() >= p){
				a += (a1[a1.length()-p] - '0') * pow(10,p-1);
			}
		}
		int b = 1;
		for(int i = 0;i < a;i++){
			b = b * 2011 % 10000;
		}
		cout << endl << b;
	}		
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
	string a1;
	int a;
	int k;
	cin >> k;
	for(int j = 0;j < k;j++){
		cin >> a1;
		a = 0;
		for(int p = 1;p <= 3;p++){
			if(a1.length() >= p){
				a += (a1[a1.length()-p] - '0') * pow(10,p-1);
			}
		}
		int b = 1;
		for(int i = 0;i < a;i++){
			b = b * 2011 % 10000;
		}
		cout << endl << b;
	}		
	return 0;
}