#include <bits/stdc++.h>
#define LIM 1000000
#define MAXN 50000

const long long MOD = 666013, MODD = 16384;
class Hash{
    public:
    int k = 0, next[MAXN + 1], lista[MODD];
    int val[MAXN + 1];
    long long d[1 + MAXN];
    inline void insert(int element, long long vl){
        k++;
        val[k] = element;
        d[k] = vl;
        next[k] = lista[element % MODD];
        lista[element % MODD] = k;
    }
    inline int find(int element){
        int p = lista[element % MODD];
        while(p != 0 && val[p] != element)
            p = next[p];
        return p;
    }
} H;

long long D(long long n){
    if(n <= 1) return 1;
    if(n > LIM){
        if(n % 2){long long x = D(n / 2); return (x * x) % MOD;}
        else return (2 * D(n / 2) * D(n / 2 - 1)) % MOD;
    }
    if(H.find(n)) return H.d[H.find(n)];
    long long ans;
    if(n % 2){long long x = D(n / 2); ans = (x * x) % MOD;}
    else ans = (2 * D(n / 2) * D(n / 2 - 1)) % MOD;
    H.insert(n, ans);
    return ans;
}

int main(){
    FILE*fi,*fo;
    fi = fopen("ciuperci.in","r");
    fo = fopen("ciuperci.out","w");

    int n;
    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++){
        long long x;
        fscanf(fi,"%lld", &x);
        fprintf(fo,"%lld\n", D(x));
    }

    return 0;
}