#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 calc2(long long c, long long p)
{
    long long rez = 1;
    while (1)
    {
        if (c==p)
            break;
        if (c==1)
            rez = (rez*p)%mod;
        if (c<=(p>>1))
            rez = rez<<1, p = p>>1;
        if (c%2)
        {
            rez = rez<<1;
            rez = rez<<(p)
        }
        else

    }
    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 = (2*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);
        //rez=calc(c,p);
        g<<rez<<"\n";
    }
    f.close();
    g.close();
    return 0;
}