#include <cstdio>

using namespace std;

const int MOD = 666013;

void getNr(long long n, long long &v1, long long &v2) {
    if (n == 1){
        v1 = 2;
        v2 = 1;
        return;
    }
    else if (n == 2) {
        v1 = 1;
        v2 = 2;
        return ;
    }

    long long r1, r2;
    if (n & 1) {
        getNr(n/2, r1, r2);
        v2 = (r2 * r2 * 1LL) % MOD;
        v1 = (2 * r1 * r2 * 1LL) % MOD;
    }
    else {
        getNr(n/2 - 1, r1, r2);
        v1 = (r1 * r1 * 1LL) % MOD;
        v2 = (2LL * r1 * r2) % MOD;
    }
}

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

    int q;
    long long n, r1, r2;

    scanf("%d", &q);
    while(q--) {
        scanf("%lld", &n);
        getNr(n, r1, r2);
        printf("%lld\n", r2);
    }

    return 0;
}