#include <cstdio>

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

bool v[55];

const int MOD=666013;

long long powder(long long a, long long p)
{
    long long rez=1;
    long long act=a;

    while(p)
    {
        if(p&1)
        {
            rez*=act;
            rez%=MOD;
        }
        p/=2;
        act=act*act;
        act%=MOD;
    }
    return rez;
}

void rezolvare()
{
    long long x;

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

    long long pow=1;

    long long pp;

    for(pp=0; pp<60; pp++)
    {
        if(pow*2-1>x)
        {
            x-=pow-1;
            break;
        }
        pow*=2;
    }

    long long nr_liber=pow;

    pow/=2;

    long long rez=1;

    while(pow)
    {
        if(x>=pow)
        {
            rez=rez*(powder(nr_liber/pow,pow));
            x-=pow;
            rez%=MOD;
            nr_liber-=nr_liber/pow;
        }
        pow/=2;
    }
    fprintf(out,"%lld\n",rez);
}

int main()
{
    int k;

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

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

    return 0;
}