#include <stdio.h>
#define modulo 666013

int x,y;

int cate_moduri(long long n){
    int x;
    if(n==1)return 1;
    if(n==2)return 2;
    if(n&1){//n impar
       x= cate_moduri(n>>1);
       return ((long long)(x)*x)%modulo;
    }
    return (((long long)cate_moduri(n>>1)*cate_moduri((n>>1)-1))<<1)%modulo;
} 


int main(){
  FILE *fin=fopen("ciuperci.in","r");
  FILE *fout=fopen("ciuperci.out","w");
  int i;
  int q;//nr de teste
  long long n;
  fscanf(fin,"%d",&q);
  for(i=0;i<q;i++){
     fscanf(fin,"%lld",&n);
     fprintf(fout,"%d\n",cate_moduri(n));
  }
return 0;
}