#include <stdio.h>
#define NIL -1
#define MOD 666013
#define MAXH 45000
#define HASH 7989
int ans[MAXH+1], next[MAXH+1], h;
long long val[MAXH+1];
int lista[HASH];
inline void adauga(long long n, int k){
    h++;
    ans[h]=k;
    val[h]=n;
    next[h]=lista[n%HASH];
    lista[n%HASH]=h;
}
inline int rasp(long long n){
    int p=lista[n%HASH];
    while((p!=0)&&(val[p]!=n)){
        p=next[p];
    }
    if(p==0){
        return NIL;
    }
    return ans[p];
}
int query(long long n){
    int r;
    if((r=rasp(n))==NIL){
        if((n&1)==1){
            r=query(n/2);
            r=r*(long long)r%MOD;
            adauga(n, r);
        }else{
            r=2LL*query(n/2)*(long long)query(n/2-1)%MOD;
            adauga(n, r);
        }
    }
    return r;
}
int main(){
    int T, t;
    long long x;
    FILE *fin, *fout;
    fin=fopen("ciuperci.in", "r");
    fout=fopen("ciuperci.out", "w");
    adauga(1, 1);
    adauga(2, 2);
    fscanf(fin, "%d", &T);
    for(t=0; t<T; t++){
        fscanf(fin, "%lld", &x);
        fprintf(fout, "%d\n", query(x));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}