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

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

long long 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)];
    }

    long long x = Solve(N/2,M/2);
    if (M&1LL)
        x = x * Solve(N/2,M/2+1) * 2 % Mod;
    else x = 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;
    while (t--)
    {
        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";
    }
}