#include <fstream>
#include <unordered_map>
#define MOD 666013
using namespace std;

typedef unordered_map <int, int> mapa;
mapa M;

int query(int n) {
    mapa :: iterator it = M.find(n);
    if (it != M.end())
        return it -> second;

    if (n & 1) {
        long long sol = query(n >> 1);
        sol *= sol;
        int md = sol % MOD;
        M[n] = md;
        return md;
    }
    else {
        long long sol = 2 * query(n >> 1) * query((n >> 1) - 1);
        int md = sol % MOD;
        M[n] = md;
        return md;
    }
}

int main () {
    ifstream cin("ciuperci.in");
    ofstream cout("ciuperci.out");

    M[1] = 1;
    M[2] = 2;

    int Q;
    cin >> Q;
    for (int i = 0 ; i < Q ; ++i) {
        int n;
        cin >> n;
        cout << query(n) << "\n";
    }

    return 0;
}