#include<bits/stdc++.h> using namespace std; char a[210]; int main() { int k,i; cin>>k; while(k--) { int m=1; int x=0; cin>>a; int len=strlen(a); if(len>3) { for(i=len-3;i<len;++i) x=x*10+a[i]-'0'; } else { for(i=0;i<len;++i) x=x*10+a[i]-'0'; } x=x%500; for(i=0;i<x;++i) { m=m*2011%10000; } cout<<m<<endl; } return 0; }