#include <fstream>

const int MOD = 666013;

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

long long N,X,K,aux,pow,T;

long long POS(long long X, int P)
{
    long long aux;
    if (X == 0)
        return 1;
    if (P <= pow)
    {
        if (X % 2 == 1)
            return (2*POS(X/2,P+1)*POS(X/2+1,P+1)) % MOD;
        else
        {
            aux = POS(X/2,P+1) % MOD;
            return aux*aux % MOD;
        }
    }
    return 1;
}

int main()
{
    f >> T;
    while (T--)
    {
        f >> N;
        aux = 1;
        pow = 0;
        while (aux - 1 <= N)
        {
            aux *= 2;
            pow++;
        }
        aux /= 2;
        pow--;

        X = N - aux + 1;

        g << POS(X,1) << '\n';
    }
    f.close();
    g.close();
    return 0;
}