#include <fstream>
#include <map>
using namespace std;
#define Mod 666013

map< pair<long long,long long>, int> H;

int Solve(long long N,long long M)
{
    if (M == 1) return N % Mod;

    if (H.find(make_pair(N,M)) != H.end()) {
        return H[make_pair(N,M)];
    }

    int x = Solve(N>>1LL,M>>1LL);
    if (M&1LL)
        x = 1LL * x * Solve(N>>1LL,(M>>1LL)+1) * 2 % Mod;
    else x = 1LL*x*x%Mod;

    H[make_pair(N,M)] = x;
    return x;
}

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

    long long N,M;
    int t,k;

    fin >> t;
    int o = 0;
    while (t--)
    {
        o++;
        if (o == 10) { H.clear(); o = 0; }
        fin >> N;
        k = 0;
        while ((1LL<<k+1)-1 < N) ++k;
        M = (1LL<<k) - (1LL<<k+1) + 1 + N;
        fout << Solve(1LL<<k,M) << "\n";
    }
}