#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int MOD = 666013;
const int HMOD = 100003;

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

int hFind(long long key) {
    for(auto it : H[key % HMOD]) {
        if(get<0>(it) == key) {
            return get<1>(it);
        }
    }
    return -1;
}

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

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

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;

    hAdd(1, 1);
    hAdd(2, 2);

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

        hReset();

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

    return 0;
}