#include <bits/stdc++.h>

using namespace std;
ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");
const int MOD = 666013;
const int MMOD = 50;
int q;
long long n;
vector <pair <long long, int> > h[MMOD];

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

    if (n == 2)
        return 2;

    int key = n % MMOD;
    for (int i = 0; i < h[key].size(); ++i) {
        if (n == h[key][i].first) return h[key][i].second;
    }

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

    h[key].push_back({n, dp});
    return dp;
}

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