#include <stdio.h>
#define NIL -1
#define MOD 666013
#define MAXH 1000
#define HASH ((1<<18)-1)
int ans[MAXH+1], next[MAXH+1], h;
long long val[MAXH+1];
short int lista[HASH+1];
FILE *fin;
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;
}
inline void init(){
    int i;
    for(i=1; i<=h; i++){
        lista[val[i]&HASH]=0;
    }
    h=0;
    adauga(1, 1);
    adauga(2, 2);
}
inline long long citeste(){
    int i=0;
    long long x=0;
    char s[20];
    fgets(s, 18, fin);
    while(s[i]!='\n'){
        x=x*10LL+s[i]-'0';
        i++;
    }
    return x;
}
int main(){
    int T, t;
    long long x;
    FILE *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++){
        x=citeste();
        fprintf(fout, "%d\n", query(x));
        init();
    }
    fclose(fin);
    fclose(fout);
    return 0;
}