#include <cstdio>

FILE* in=fopen("ciuperci.in","r");
FILE* out=fopen("ciuperci.out","w");

bool v[55];

const int MOD=666013;

void back(long long x, long long y, long long &rez1, long long &rez2)
{
    if(x<=2 && y<=2)
    {
        rez1=x;
        rez2=y;
        return;
    }

    long long r1,r2;

    back(x/2,x/2-1,r1,r2);

    if(x&1)
    {
        rez1=r1*r1;
        rez1%=MOD;

        rez2=r1*r2*2;
        rez2%=MOD;
    }
    else
    {
        rez1=r1*r2*2;
        rez1%=MOD;

        rez2=r2*r2;
        rez2%=MOD;
    }

}

void rezolvare()
{
    long long x,rez,aux;

    fscanf(in,"%lld",&x);

    back(x,x-1,rez,aux);

    fprintf(out,"%lld\n",rez);

}

int main()
{
    int k;

    fscanf(in,"%d",&k);

    for(int i=1; i<=k; i++)
    {
        rezolvare();
    }

    return 0;
}