#include<stdio.h>
#include<algorithm>
#define BUFFER_SIZE 8192
using namespace std;
long long maxnum;
long long o;
long long k=1;
long long v[101010];
long long z=666013;
int doipre[101010];
char buff[BUFFER_SIZE];
int buffIt;
FILE *inputFile = fopen("ciuperci.in", "r");

inline long long getNumber() {
  long long ret = 0;

  while (buff[buffIt] < '0' || buff[buffIt] > '9')
    if (++buffIt == BUFFER_SIZE)
      fread(buff, BUFFER_SIZE, 1, inputFile),
      buffIt = 0;

  while (buff[buffIt] >= '0' && buff[buffIt] <= '9') {
    ret = ret * 10 + buff[buffIt] - '0';

    if (++buffIt == BUFFER_SIZE) {
      buffIt = 0;
      fread(buff, BUFFER_SIZE, 1, inputFile);
    }
  }


  return ret;
}
long long put(long long y)
{   if(y<100000)
        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;
    }
}
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;
}
int 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((num-1)%(z-1));
    }
    else if(num<=lung/2)
    {
        return put((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);
N=getNumber();
doipre[0]=1;
for(int i=1;i<=100000;++i)
{
    doipre[i]=doipre[i-1]*2;
    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)
        {
        long long x;
            x=getNumber();
           printf("%d\n",rec(x));
        }


return 0;
}