#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(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);
    //out<<x<<" ";
    return (((long long)(((long long) x*x)%666013)*2))%666013;
}
int putere3(long long n, long long k)
{
    int x;
    if(k==0)
        return 1;
    if(k%2==0)
    {
        x=putere3(n,k/2);
        return ((((long long) x)*x)%666013);
    }
    x=putere3(n,k/2);
    return (((long long) (((long long) x*x)%666013))*n)%666013;
}

int arbore(long long p, long long nrp, long long ip, long long nrip, int niv)
{
    int par=0,impar=0,nrpar=0,nrimpar=0,i,rez,a,b;
    if(p==0 && ip==1)
    {
        a=putere2(k-niv+1);
        b=putere3(a,nrip);
        return b;
    }
    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;
        }
    }
    a=putere2(nrip);
    rez=(((long long) a)*arbore(par,nrpar,impar,nrimpar,niv+1))%666013;
    //out<<a<<" "<<rez<<" "<<niv<<"\n";
    return rez;
}


int main()
{
    int t,i;
    long long 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;
}