#include<cstdio>

const int MOD = 666013;
const int N = 200001;

int d[N];

long long arbore(long long x) {
    if (x < N)
        return d[x];

    if (x & 1) {
        long long rez = arbore(x / 2);
        return (long long)rez * rez % MOD;
    }

    return (long long)arbore(x / 2 - 1) * arbore(x / 2) % MOD * 2 % MOD;
}

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

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

void dinamica() {
    d[1] = 1;
    d[2] = 2;
    for (int i = 3; i < N; ++i)
        if (i & 1)
            d[i] = (1LL * d[i / 2] * d[i / 2]) % MOD;
        else
            d[i] = (1LL * d[i / 2 - 1] * d[i / 2]) % MOD * 2 % MOD;
}

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

    dinamica();

    rez();

    return 0;
}