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

long long N,M,R,pow;
int t,k;
long long Ans;

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

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

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

    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";
    }
}