#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define ll long long

using namespace std;

const int MOD = 666013;
const int N = 32;

vector < pair < ll, int > > a[N]; // creez o matrice a pentru a retine valorile deja calculate.

inline int cauta(ll x, int exp) {
    for (int i = 0; i < (int)a[exp].size(); ++i)
        if (a[exp][i].first == x)
            return a[exp][i].second;

    return -1;
}

inline int arbore(long long x) {
    if (x == 1)
        return 1;

    if (x == 2)
        return 2;

    int putere = x & 31, rez = cauta(x, putere); // caut in matricea a daca am calculat deja valoarea pentru x

    if (rez != -1) // daca am calculat, o afisez
        return rez;

    if (x & 1) {
        rez = arbore(x / 2);
        rez = rez * rez % MOD;
    }
    else
        rez = (ll)arbore(x / 2) * arbore(x / 2 - 1) % MOD * 2 % MOD;

    a[putere].push_back(make_pair(x, rez)); // adaug in matrice rez ca valoare calculata pentru x

    return rez;
}

void sterg() {
    for (int i = 0; i < N; ++i)
        a[i].clear();
}

void solve() {
    int t;
    scanf("%d", &t);

    for (int i = 1; i <= t; ++i) {
        long long n;
        scanf("%lld", &n);
        printf("%d\n", arbore(n));

        sterg();
    }
}

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

    solve();

    return 0;
}