#include <stdio.h>
#include <stdlib.h>
#define MOD 2000
#define MOD2 666013
#define MAXN 2000

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

int k, next[MAXN+1], lista[MOD];
long long val[MAXN+1], d[MAXN+1];
inline void insert(long long x, long long y){
    k++;
    val[k]=x;
    d[k]=y;
    next[k]=lista[x%MOD];
    lista[x%MOD]=k;
}
/*inline void erase(int x){
    int p=lista[x%MOD];
    if(p==0){
        return ;
    }
    if(val[p]==x){
        lista[x%MOD]=next[lista[x%MOD]];
        ans++;
        return ;
    }
    while((next[p]!=0)&&(val[next[p]]!=x)){
        p=next[p];
    }
    if(next[p]!=0){
        next[p]=next[next[p]];
        ans++;
    }
}*/
inline int find(int x){
    int p=lista[x%MOD];
    if(p==0)
        return -1;
    if(val[p]==x)
        return p;
    while(next[p]!=0 && val[next[p]]!=x)
        p=next[p];
    if(next[p]!=0)
        return p;
    return -1;
}

long long D(long long x){
    if(find(x)==-1){
        insert(x, 0);
        if(x%2==1)
            d[find(x)]=(D(x/2)*D(x/2))%MOD2;
        else
            d[find(x)]=(2*D(x/2)*D(x/2-1))%MOD2;
    }
    return d[find(x)];
}

int main(){
    fi=fopen("ciuperci.in","r");
    fo=fopen("ciuperci.out","w");
    long long n=nextnum();
    insert(0, 1);
    insert (1, 1);
    for(int i=0;i<n;i++){
        long long x=nextnum();
        fprintf(fo,"%lld\n", D(x));
    }
    fclose(fi);
    fclose(fo);
    return 0;
}