#include <stdio.h>
#define modulo 666013

int x,y;

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