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