#include <fstream>
#include <map>
#include <algorithm>

using namespace std;

ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

const int MOD = 666013;

map < long long, int > H;

int getNr(long long n) {
    int v1, v2, val;

    if(H.find(n) != H.end()) {
        return H.find(n) -> second;
    }
    else {
        v1 = getNr(n / 2);
        if(n & 1) {
            val = (1LL * v1 * v1) % MOD;
        }
        else {
            v2 = getNr((n - 1)/2);
            val = (1LL * 2 * v1 * v2) % MOD;
        }
        H[n] = val;
        return val;
    }
}

int main() {
    int q, i, j = 0;
    long long n;

    H[1] = 1;
    H[2] = 2;

    in >> q;
    while(q--) {
        in >> n;

        if(j == 375) {
            H.clear();
            H[1] = 1;
            H[2] = 2;
            j = 0;
        }
        else j++;

        out << getNr(n) << '\n';
    }

    return 0;
}