#include<stdio.h>
int o;
long long k=1;
int v[101010];
long long z=666013;
long long put(long long x,long long y)
{
    if(y==0)
        return 1;
    long long w;
    if(y==1)
        return x;
    else if(y%2==0)
    {
        w=put(x,y/2);
        return (w*w)%z;
    }
    else
    {
        w=put(x,y-1)%z;
        return (w*x)%z;
    }
}
long long rec(long long k)
{
//printf("%lld\n",k);
if(k==0)
    return 1;
if(k==1)
    return 1;
if(k==2)
    return 2;
int p=1;
while(v[p]<=k)
        {//printf("!");
            ++p;
        }

    --p;
    long long num=k-v[p]+1;
    long long lung=v[p+1]-v[p];
   // printf("%lld %d!\n",num,p);
    if(num==1)
        return 1;
    if(num==lung/2+1)
    {
        return put(2,num-1);
    }
    else if(num<=lung/2)
    {
        return put(2,num-1)*rec(k-(v[p]-v[p-1]))%z;
    }
    else
    {
        long long mij=lung/2+1;
        return rec(k-(num-mij)*2)%z;
    }
}
int N;
int main()
{
freopen("ciuperci.in","r",stdin);
freopen("ciuperci.out","w",stdout);
scanf("%d",&N);
for(long long i=1;i<=10000000000000000;i+=k)
    {
    v[++o]=i;
    //printf("%d\n",o);
    k*=2;
    }
    //for(int i=1;i<=9;++i)
       // printf("%d ",v[i]);
        for(int i=1;i<=N;++i)
        {
        long long x;
        scanf("%lld",&x);
           printf("%lld\n",rec(x));
        }
return 0;
}