#include <bits/stdc++.h>

using namespace std;
ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");
const int MOD = 666013;
int q;
long long n;

long long rezolvare(long long n) {
    if (n == 1)
        return 1;

    if (n == 2)
        return 2;


    long long dp;
    dp = rezolvare((n - 1) / 2) % MOD;
    if (n % 2) {
        dp = (dp * dp) % MOD;
    }
    else {
        dp = (dp * rezolvare((n - 1) / 2 + 1) * 2) % MOD;
    }

    return dp;
}

int main()
{
    fin >> q;
    while(q--){
        fin >> n;
        fout << rezolvare(n) % MOD << '\n';
    }
    return 0;
}