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

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

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 << M << " " << k << " ";
        R = M/2 + M%2;
        pow = M*k - R*(R+1) + R*(M%2);
        if (M%2 != 0) pow++;
        //fout << pow << "\n";
        //return 0;
        Ans = 1; x = 2;
        while (pow) {
            if (pow%2==1)
                Ans = Ans * x % Mod;
            x = x * x % Mod;
            pow /= 2;
        }

        fout << Ans << "\n";
    }
}