#include <iostream>
#include <fstream>
#define i64 long long

using namespace std;

const int nmax = 100000;
const int mod = 666013;
int Rez[nmax];
i64 P[64];

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

int M(int N)
{
    int i;
    int T;
    if(N < nmax && Rez[N] != 0)
        return Rez[N];
    for(i = 0; i <= 63; i++)
        if(P[i] - 1 >= N) break;

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

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

    if(N < nmax)
        Rez[N] = T;

    return T;
}

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

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

    return 0;
}