#include<iostream> #include<cstring> #include<cstdio> using namespace std; char a[210]; int f(int k){ if(k==0) return 1; else if(k%2==1) return f(k-1)*2011%10000; else{ int num=f(k/2)%10000; return num*num%10000; } } int main() { int t,n,m; cin>>t; while(t--){ cin>>a; n=strlen(a); m=a[n-1]-'0'; if(n>=2) m+=(a[n-2]-'0')*10; if(n>=3) m+=(a[n-3]-'0')*100; if(n>=4) m+=(a[n-4]-'0')*1000; cout<<f(m)<<endl; } return 0; }