#include<stdio.h>
#include<algorithm>
#include<fstream>
#include<iostream>
using namespace std;
long long maxnum;
long long o;
long long k=1;
long long v[101];
long long z=666013;
int consta=10000;
int doipre[10010];
int put(long long y)
{   if(y<consta)
        return doipre[y];
    long long x=2;
    if(y==0)
        return 1;
    long long w;
    if(y==1)
        return x;
    else if(y%2==0)
    {
        w=put(y/2);
        return (w*w)%z;
    }
    else
    {
        w=put(y-1)%z;
        return (w*x)%z;
    }
}
int cautbin(long long q)
{
    int st=1,dr=o;
    int 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 0;
if(k==1)
    return 0;
if(k==2)
    return 1;
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 (num-1);
    }
    if(num>lung/2+1)
    {
        long long mij=lung/2+1;
        return rec(k-(num-mij)*2);

    }
    if(num<=lung/2)
    {
        return ((num-1)+rec(k-(v[p]-v[p-1])));
    }

}

long long x;
long long N;
int main()
{
ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");
fin>>N;
doipre[0]=1;
for(int i=1;i<=consta;++i)
{
    doipre[i]=doipre[i-1]*2;
   // if(doipre[i]>666013)
    doipre[i]=doipre[i]%666013;
   // printf("%d\n",v[i]);
}
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)
        {
            fin>>x;
           fout<<put(rec(x)%(z-1))<<"\n";
        }


return 0;
}