#include <cstdio>
#include <vector>

#define Mod 666013
#define LL long long
#define U 31
#define n first
#define s second

using namespace std;

vector < pair <LL, int> > H[U];

inline int Search (LL X)
{
    int Key=X%U;
    for (int i=0; i<(int)H[Key].size (); ++i)
    {
        if (X==H[Key][i].n)
        {
            return H[Key][i].s;
        }
    }
    return -1;
}

inline void Insert (pair <LL, int> X)
{
    int Key=X.n%U;
    for (int i=0; i<(int)H[Key].size (); ++i)
    {
        if (X.n==H[Key][i].n)
        {
            H[Key][i].s+=X.s;
            return;
        }
    }
    H[Key].push_back (X);
}

int Query (LL N)
{
    if (N<=2) return N;
    int S=Search (N);
    if (S!=-1)
    {
        return S;
    }
    if (N&1)
    {
        S=Query ((N-1)/2);
        S=(1LL*S*S)%Mod;
    }
    else
    {
        int SL=Query ((N-1)/2);
        int SR=Query ((N-1)/2+1);
        S=(1LL*2*SL*SR)%Mod;
    }
    Insert (make_pair (N, S));
    return S;
}

int main()
{
    freopen ("ciuperci.in", "r", stdin);
    freopen ("ciuperci.out", "w", stdout);
    int NQ;
    scanf ("%d", &NQ);
    for (; NQ>0; --NQ)
    {
        LL N=0;
        scanf ("%lld", &N);
        printf ("%d\n", Query (N));
        for (int i=0; i<U; ++i)
        {
            H[i].clear ();
        }
    }
    return 0;
}