#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("ciuperci.in");
ofstream out ("ciuperci.out");

int k;
long long rez;

long long putere(long long n)
{
    long long i;
    k=0;
    for(i=1;i*2-1<=n;i*=2)
    {
        k++;
    }
    return i-1;
}

int putere2(long long k)
{
    int x;
    if(k==0)
        return 1;
    if(k%2==0)
    {
        x=putere2(k/2);
        return (((long long) x)* x)%666013;
    }
    x=putere2(k/2);
    return (((long long)(((long long) x*x)%666013)*2))%666013;
}

void arbore(long long p, long long nrp, long long ip, long long nrip, int niv)
{
    long long par=0,impar=0,nrpar=0,nrimpar=0;
    if(p==0 && ip==1)
    {
        rez+=(k-niv+1)*nrip;
        return;
    }
    if((p/2)%2==0)
    {
        par=p/2;
        nrpar=nrp*2;
    }
    else
    {
        impar=p/2;
        nrimpar=nrp*2;
    }
    if(nrip!=0)
    {
        if((ip/2)%2==0)
        {
            impar=ip/2+1;
            nrimpar+=nrip;
            par=ip/2;
            nrpar+=nrip;
        }
        else
        {
            impar=ip/2;
            nrimpar+=nrip;
            par=ip/2+1;
            nrpar+=nrip;
        }
    }
    rez+=nrip;
    arbore(par,nrpar,impar,nrimpar,niv+1);
    return;
}

int main()
{
    int t,i;
    long long n, m;
    in>>t;
    for(i=1;i<=t;++i)
    {
        rez=0;
        in>>n;
        m=n-putere(n);
        if(m==0)
        {
            out<<"1\n";
            continue;
        }
        if(m%2==0)
            arbore(m,1,0,0,1);
        else
            arbore(0,0,m,1,1);
        out<<putere2(rez)<<"\n";
    }
    return 0;
}