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

long long log_put(long long n,long long p) {
    if (p == 0) return 1;
    if (p&1LL) return n*log_put(n*n%Mod,p>>1LL)%Mod;
    return log_put(n*n%Mod,p>>1LL);
}

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

    int t;
    fin >> t;
    while (t--) {
        long long N;
        fin >> N;
        int k = 0;
        while ((1LL<<k+1)-1 < N) ++k;
        long long M = (1LL<<k) - (1LL<<k+1) + 1 + N;
        //fout << M << " " << k << " ";
        long long R = M/2 + M%2;
        long long pow = M*k - R*(R+1) + R*(M%2);
        if (M%2 != 0) pow++;
        //fout << pow << "\n";
        //return 0;
        fout << log_put(2,pow) << "\n";
    }
}