#include <stdio.h>
#define modulo 666013


int cate_moduri(long long n){
    int x,y;
    if(n==1)return 1;
    if(n==2)return 2;
    if(n%2==1){
       x=cate_moduri(n/2);
       return (((long long)(x))*x)%modulo;
    }
    //daca n e par
    x=cate_moduri(n/2);
    y=cate_moduri(n/2-1);
    return (2*(long long)(x)*y)%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;
}