#include<cstdio>

const int MOD = 666013;

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

    if (x == 2)
        return 2;

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

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

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

    rez();

    return 0;
}