# include <cstdio>

typedef long long ll;
const char *FIN = "ciuperci.in", *FOU = "ciuperci.out";
const int MOD = 666013;

int T;
ll N;

inline int rez (ll N) {
    if (N == 0 || N == 1) return 1;
    int aux = rez (N >> 1) % MOD;
    if (N & 1)
        return (aux * aux) % MOD;
    return (aux * rez ((N >> 1) - 1) << 1) % MOD;
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    for (scanf ("%d", &T); T; --T) {
        scanf ("%lld", &N);
        printf ("%d\n", rez (N));
    }
}