#include <iostream>
#include <fstream>
#include <vector>
#define i64 long long
#define TR(C, i)\
    for(i = C.begin();i < C.end(); i++)
#define ft first
#define sc second
#define pb push_back
#define mp make_pair

using namespace std;

const int K = 10007;
const int mod = 666013;
i64 P[64];

vector< pair<i64, i64> > G[K];
vector< pair<i64, i64> >::iterator it;

void calc()
{
    P[0] = 1;
    for(int i = 1; i < 64; i++)
        P[i] = P[i - 1] << 1;
}

i64 M(int N)
{
    int i, step;
    TR(G[N % K], it)
        if(it->ft == N)
            return it->sc;

    for(i = 0, step = 32; step > 0; step >>=1 )
        if(P[i + step] - 1 <= N) i += step;

    i64 put = P[i] - 1;
    i64 diff = N - put;

    i64 T = (M((diff >> 1) + (put >> 1)) * M((diff >> 1) + (put >> 1) + (diff & 1))) % mod;
    if(diff & 1)
        T = (T << 1) % mod;

    G[N % K].pb(mp(N, T));
    return T;
}

int main()
{
    ifstream in("ciuperci.in");
    ofstream out("ciuperci.out");

    calc();
    i64 Q, N;
    in >> Q;
    G[1].pb(mp(1, 1));
    G[2].pb(mp(2, 2));
    G[3].pb(mp(3, 1));
    while(Q--)
    {
        in >> N;
        out << M(N) << '\n';
    }

    return 0;
}