#include <fstream>
#include <vector>

const int MOD = 666013;

using namespace std;
ifstream f("ciuperci.in");
ofstream g("ciuperci.out");

long N,Q;
vector <long long> H[100],HH[100];

int HASH(long long X)
{
    long long aux;
    aux = (X*3+123)%100;
    return aux;
}

long long SOL(int X)
{
    long long A,B;
    int aux;
    bool ok = false;
    aux = HASH(X);
    if (X == 2)
        return 2;
    if (X == 1)
        return 1;
    for (int i = 0; i < H[aux].size(); ++i)
    {
        if (H[aux][i] == X)
        {
            A = HH[aux][i];
            ok = true;
            return HH[aux][i];
        }
    }
    if (!ok)
    {
        if (X % 2 == 1)
        {
            A = SOL(X/2);
            H[aux].push_back(X);
            HH[aux].push_back(A*A%MOD);
            return A*A % MOD;
        }
        else
        {
            A = SOL(X/2);
            B = SOL(X/2-1);
            H[aux].push_back(X);
            HH[aux].push_back(2*A*B%MOD);
            return 2*A*B % MOD;
        }
    }
}

int main()
{
    f >> Q;
    while (Q--)
    {
        f >> N;
        for (int i = 1; i <= 100; ++i)
        {
            while(!H[i].empty())
            {
                H[i].pop_back();
                HH[i].pop_back();
            }
        }
        g << SOL(N) << '\n';
    }
    f.close();
    g.close();
    return 0;
}