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

signed main(){
  int a,b;
  string a1;
   cin>>a;
  
   while(a--){
      cin>>a1;   
   
      b=0;
      
         
         if(a1.length()>3){
            for(int i=a1.length()-3;i<a1.length();i++)
               b=(a1[i]-'0')+b*10;
         }
         else{
            for(int i=0;i<a1.length();i++)
               b=(a1[i]-'0')+b*10;
         }
         int c=1;
         b%=4000;
         for(int i=1;i<=b;i++){
            c=c*2011%10000;
         }
         
         

      
      cout<<c<<endl;
      // c=1;
   }



   return 0; 
}