#include <stdio.h>
#include <stdlib.h>
#define modulo 666013
#define MAXIM 10005

int pozitie=MAXIM-1;
char buff[MAXIM];//citesc bucati de cate maxim 10005 caractere

void cit(long long &nr){
    nr=0;
    while(buff[pozitie]<'0' || buff[pozitie]>'9')//cat timp nu e cifra, treci mai departe
        if (++pozitie==MAXIM){
            fread (buff,1,MAXIM,stdin);
            pozitie=0;
        }
    while('0'<=buff[pozitie] && buff[pozitie]<='9'){//cat timp e cifra
        nr=nr*10+buff[pozitie]-'0';
        if (++pozitie==MAXIM){
            fread (buff,1,MAXIM,stdin);
            pozitie=0;
        }
     }
}



void pInvers(long long a, long long b, long long &u, long long &v) {
 if(b==0) {
  u=1; v=0;
 } else {
  long long p, q;
  pInvers(b, a%b, p, q); 
  u=q; v=p-(a/b)*q;
 }
}

long long Comb(long long n, long long k) {
 long long u, v;
 if(k==0 || k==n) return 1;
 pInvers(modulo, k, u, v);
 if(v<0)v+=modulo;
 return (((n*Comb(n-1, k-1))%modulo)*v)%modulo;
}

int ase(long long n) {
 long long m, k=-1, w=n;
 if(n==1)return 1;
 while(w) {w>>=1; k++;} m=(1<<(k-1)); k=(n>>1)-m;
 //printf("n=%d, m=%d, k=%d\n", n, m, k);
 w=Comb(m, k+1);
 if(n%2) 
  return((w*w)%modulo);
 else {
  return(2*w*Comb(m, k))%modulo;
 } 
}

int main() {
/*
 long k=atoi(argv[1]), x0, y0;
 pInvers(modulo, k, x0, y0);
 printf("Inversul lui k=%d este x0=%d\n", k, y0>0?y0:y0+modulo);
*/
// printf("Comb(%d,%d)=%d\n", atoi(argv[1]), atoi(argv[2]), Comb(atoi(argv[1]), atoi(argv[2])));
  freopen("ciuperci.in","r",stdin);
  freopen("ciuperci.out","w",stdout);
  long long q;
  long long i,n;  
  cit(q);
  for(i=0;i<q;i++){
    cit(n);//printf("%lld",n);
    printf("%d\n",ase(n));
  }
  

// printf("ase(%d)=%d\n", atoi(argv[1]), ase(atoi(argv[1])));
 return 0;
}