#include <fstream>
#include <algorithm>

using namespace std;

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

const int MOD = 666013;
const int HMOD = 4133;
const int RESET_THRESHOLD = 4133;

struct hashElement {
    long long key;
    int val;
};

int nrH;
vector < hashElement > H[HMOD];

inline int hFind(long long key) {
    for(auto it : H[key % HMOD]) {
        if(it.key == key) {
            return it.val;
        }
    }
    return -1;
}

inline void hAdd(long long key, int val) {
    nrH++;
    if(hFind(key) == -1) {
        H[key % HMOD].push_back(hashElement{key, val});
    }
}

inline void hReset() {
    nrH = 0;
    for(register int i = 0; i < HMOD; i++) {
        H[i].clear();
    }
    hAdd(1, 1);
    hAdd(2, 2);
}

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

    val = hFind(n);
    if(val != -1) {
        return val;
    }
    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;
        }
        hAdd(n, val);
        return val;
    }
}

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

    hReset();

    in >> q;
    while(q--) {
        in >> n;
        out << getNr(n) << '\n';
        if(nrH > RESET_THRESHOLD) hReset();
    }

    return 0;
}