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

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

long long Solve(long long N,long long M)
{
    if (M == 1) return N % Mod;
    return 1LL*Solve(N/2,M/2+M%2)*Solve(N/2,M/2)*(M%2?2:1) % Mod;
}

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

    fin >> t;
    while (t--)
    {
        fin >> N;
        while ((1LL<<k+1)-1 < N) ++k;
        M = (1LL<<k) - (1LL<<k+1) + 1 + N;
        fout << Solve(1LL<<k,M) << "\n";
    }
}