#include <fstream>
#include <algorithm>

using namespace std;

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

const int MOD = 666013;
const int HMOD = 350;

vector < pair < long long, int > > H[HMOD];

inline int hFind(long long X) {
    int key = X % HMOD;
    register int i;
    for(i = 0; i < H[key].size(); i++) {
        if(get<0>(H[key][i]) == X) {
            return get<1>(H[key][i]);
        }
    }
    return -1;
}

inline void hAdd(pair < long long, int > X) {
    int key = get<0>(X) % HMOD;
    register int i;
    for(i = 0; i < H[key].size(); i++) {
        if(get<0>(H[key][i]) == get<0>(X)) {
            return;
        }
    }
    H[key].push_back(X);
}

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

    val = hFind(n);
    if(n <= 2) {
        return n;
    }
    else if(val != -1) {
        return val;
    }
    else {
        v1 = getNr(n / 2);
        if(n & 1) {
            val = (1LL * v1 * v1) % MOD;
        }
        else {
            int v2 = getNr((n - 1)/2);
            val = (2LL * v1 * v2) % MOD;
        }
        hAdd(make_pair(n, val));
        return val;
    }
}

int main() {
    int q;
    long long n;
    register int i;

    in >> q;
    while(q--) {
        in >> n;
        out << getNr(n) << '\n';
        for(i = 0; i < HMOD; i++) H[i].clear();
    }

    return 0;
}