#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>

using namespace std;

#define MOD 666013

long long Q, N, x, y;

// N = numarul curent de noduri
// x = T(N)
// y = T(N + 1)
// T(N) = raspunsul la intrebare pentru N
//
//        / T((N - 1) / 2) ^ 2, N - impar
// T(N) =
//        \ 2 * T(N / 2) * T(N / 2 - 1), N - par

void doit(long long N, long long &x, long long &y) {
    long long xx, yy;

    if(N == 0) {
        x = 1; y = 1; return;
    }
    if(N == 1) {
        x = 1; y = 2; return;
    }

    doit((N - 1) / 2, xx, yy);

    if(N & 1) {
        x = (xx * xx) % MOD;
        y = (2LL * xx * yy) % MOD;
    }
    else {
        x = (2LL * xx * yy) % MOD;
        y = (yy * yy) % MOD;
    }
}

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

    scanf("%lld", &Q);

    while(Q--) {
        scanf("%lld", &N);

        doit(N, x, y);

        printf("%lld\n", x);
    }

	return 0;
}