#include<stdio.h>
#include<algorithm>
using namespace std;
long long maxnum;
long long o;
long long k=1;
long long 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 cautbin(long long q)
{
    long long st=1,dr=o;
    long long ras=0,mij;
    while(st<=dr)
    {

        mij=(st+dr)/2;
        if(v[mij]>=q)
            {
            dr=mij-1;
            ras=mij;
            }
        else
        {
        st=mij+1;
        }
    }
    return ras;
}
long long rec(long long k)
{
//printf("%lld\n",k);
//prlong longf("%lld\n",k);
if(k==0)
    return 1;
if(k==1)
    return 1;
if(k==2)
    return 2;
long long p=0 ;
long long q;
q=cautbin(k);

    --q;
    p=q;
   // printf("%lld %d\n",p,q);
    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)%(z-1));
    }
    else if(num<=lung/2)
    {
        return put(2,(num-1)%(z-1))*rec(k-(v[p]-v[p-1]))%z;
    }
    else
    {
        long long mij=lung/2+1;
        return rec(k-(num-mij)*2)%z;
    }
}
long long N;
int main()
{
freopen("ciuperci.in","r",stdin);
freopen("ciuperci.out","w",stdout);
scanf("%d",&N);
for(long long i=1;i<=1LL*30000000000000000;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;
}