#include <iostream>
#include <fstream>

using namespace std;

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


int k;

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


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


int arbore(int p, int nrp, int ip, int nrip,int niv)
{
    int par=0,impar=0,nrpar=0,nrimpar=0,i,rez;
    if(p==0 && ip==1)
    {
        rez=1;
        for(i=1;i<=nrip;++i)
            rez=(rez*putere2(k-niv+1))%666013;
        return rez;

    }
    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;
        }
    }
    return (putere2(nrip)*arbore(par,nrpar,impar,nrimpar,niv+1))%666013;
}


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