#include<cstdio>
using namespace std;
FILE*in=fopen("ciuperci.in","r");
FILE*out=fopen("ciuperci.out","w");
int q,i;
long long n,v1,v2,w1,w2,a,b,r;
const int mod=666013;
long long f(long long p)
{
    long long o=2;
    long long rr=1;
    while(p>0)
    {
        if(p%2==1)
        {
            rr=(long long)(rr*o);
            rr=(long long)(rr%mod);
        }
        o=(long long)(o*o);
        o=(long long)(o%mod);
        p=(long long)(p/2);
    }
    return rr;
}
int main()
{
    fscanf(in,"%d",&q);
    for(i=1;i<=q;i++)
    {
        r=0;
        fscanf(in,"%lld",&n);
        a=1;
        b=0;
        v1=(long long)n;
        while(v1>0)
        {
            w2=(long long)((long long)((long long)(v1-1)/2)+1);
            w1=(long long)((long long)(v1-1)/2);
            if(v1%2==1)
            {
                a=(long long)((long long)(2*a)+b);
                r=(long long)(b+r);
            }
            else
            {
                b=(long long)((long long)(2*b)+a);
                r=(long long)(r+a);
            }
            v2=(long long)w2;
            v1=(long long)w1;
        }
        fprintf(out,"%lld\n",f(r));
    }
}