#include <cstdio>
#include <algorithm>

using namespace std;

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

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

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;
    }
}

inline long long atoll() {
    long long x = 0, i;
    for(i = 0; BUFF[i] != NULL; i++) {
        x = x * 10 + BUFF[i] - '0';
    }
    return x;
}

int main() {
    freopen("ciuperci.in", "r", stdin);
    freopen("ciuperci.out", "w", stdout);

    int q;
    long long n;
    register int i;

    scanf("%d\n", &q);
    while(q--) {
        gets(BUFF);
        n = atoll(BUFF);
        printf("%d\n", getNr(n));
        for(i = 0; i < HMOD; i++) H[i].clear();
    }

    return 0;
}