# include <cstdio>
# include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx ;

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

int T;
ll N;

hash_map <int, int> M;

/*inline int calcul(ll n) {
    if (n==0)
        return 1;
    if (n==1)
        return 1;
    int act=find(n);
    if (act!=-1)
        return act;
    if (n % 2==1)
        act=((ll)calcul(n/2)*calcul(n/2))%MOD;
    else
        act=((ll)calcul(n/2)*calcul(n/2-1)*2)%MOD;
    A[++r].f=n;
    A[r].s=act;
    return act;
}*/

int rez (ll N) {
    if (N == 0 || N == 1) return 1;
    if (M.count (N) > 0) return M[N];
    int aux = rez (N >> 1);
    if (N & 1)
        aux = (1LL * aux * aux) % MOD;
    else aux = (1LL * aux * rez ((N >> 1) - 1) << 1) % MOD;
    M[N] = aux;
    return aux;
}

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

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