#include <stdio.h>
#define modulo 666013


int comb(long long n, long long k){
    if(n==0 || k>n)return 0;
    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;//2^(log in baza 2 din n)
    int i;
    for(i=0;i<sizeof(long long);i++){
        if((n&(1<<i))!=0)x=i;
    }
    x=1<<x;
    return comb(x,n+1-x);
}

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;
}