#include<fstream>
using namespace std;
int num[15110];
int nrfin;
long long rec(long long x)
{

if(x==1||x==0)
    return 1;
if(x<nrfin)
    return num[x];
    long long q=rec(x/2);
    if(x%2==0)
        return (q*rec(x/2-1)*2)%666013;
    else return (q*q)%666013;
}
long long N,x;
int main()
{
ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");
    num[0]=num[1]=1;
    for(int i=1;i<=10010;++i)
        {
        num[i]=rec(i);
        nrfin=i;
    }
    fin>>N;
        for(int i=1;i<=N;++i)
        {
            fin>>x;
            fout<<rec(x)<<"\n";
            //printf("%lld\n",rec(x));
        }
}