#include <fstream>
#include <queue>
#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 x,rez=1,next=2,pasi=1;
    queue <long long> q;
    q.push(c);
    do
    {
        x = q.front();
        q.pop();
        pasi++;
        if (x==1)
            rez = (rez*p)%mod;
        else
        {
            if (x!=p)
            {
                if (x%2)
                {
                    rez = (rez<<1)%mod;
                    q.push(x>>1);
                    q.push((x>>1)+1);
                }
                else
                {
                    q.push(x>>1);
                    q.push(x>>1);
                }
            }
        }
        if(pasi==next)
            p=p>>1,next=next<<1;
    }while(!q.empty());
    return rez;
}
long long calc(long long c,long long p)
{
    long long rez;
    if ((c<<1)==p)
        return (1<<c)%mod;
    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);
        g<<rez<<"\n";
//        rez=calc2(c,p);
//        g<<rez<<"\n";
    }
    f.close();
    g.close();
    return 0;
}