#include <stdio.h>
#define modulo 666013


int comb(long long n, long long k){
//    if(k>n)return 0;
    if(k==0 || k==n)return 1;
    if(k==1)return n%modulo;
    return (comb(n-1,k)+comb(n-1,k-1))%modulo;
}

int cate_moduri(long long n){
    int x=0;
    long long i;
    //cate noduri ocupa deja un abore complet? x
    int copie=n+1;
    for(i=0;i<sizeof(long long);i++){
        if((copie&(1<<i))!=0)x=(int)(i);
    }
    x=1<<x;
    i=n+1-x;
    printf("n=%d, arborele complet are %d noduri\n",n,x);
    if(i==0)return 1;
//    x=x<<1;
//    printf("n=%lld am x=%d spatii libere si trebuie sa repartizez %d noduri\n",n,x,i);
    if(i==1)return x%modulo;
    if(i&1){
       //e impar
       i=i>>1;
       //printf("2*combin(%d,%d)*combin(%d,%d)\n",x,i,x,i-1);
       return (((long long)2)*comb(x>>1,i)*comb(x>>1,i+1))%modulo;
       //return 0;
    }
    i=i>>1;
    i=comb(x>>1,i);
      //printf("(combin(%d,%d))^2\n",x,i);
//return 0;
      return (i*i)%modulo;
}

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