#include <fstream>
#define mod 666013

using namespace std;

inline long long log2(long long n)
{
    long long rez=0;
    while (n)
    {
        n=n>>1;
        rez++;
    }
    return rez;
}

long long calc(long long c,long long p)
{
    long long rez;
    if (c==1)
        return p%mod;
    if (p==c)
        return 1;
    if (c%2)
        rez = (calc(c>>1,p>>1)*calc((c>>1)+1,p>>1))%mod;
    else
    {
        rez = calc(c>>1,p>>1);
        rez = (rez*rez)%mod;
    }
    return rez;
}

int main()
{
    ifstream f("ciuperci.in");
    ofstream g("ciuperci.out");
    long long q,n,i;
    long long p,c;
    long long rez;
    f>>q;
    for (i=0;i<q;i++)
    {
        f>>n;
        p=log2(n)-1;
        c=n -(1<<p)+1;
        p=1<<p;
        rez=calc(c,p);
        g<<rez<<"\n";
    }
    f.close();
    g.close();
    return 0;
}