#include <stdio.h>
#define LOGMAX 54
#define MOD 9997
#define MOD2 666012
int ult[MOD], hnext[2 * LOGMAX + 1], dr;
long long hrez[2 * LOGMAX + 1], hn[2 * LOGMAX + 1];

int caut(long long n){
  int poz = ult[n % MOD];
  while(poz > 0 && hn[poz] != n)
    poz = hnext[poz];
  return poz;
}

long long nrarb(long long n){
  if(n == 1 || n == 0)
    return 1;
  long long x = caut(n);
  if(x != 0)
    return hrez[x];
  long long rez;
  n--;
  if(n & 1)
    rez = 2 * nrarb(n / 2 + 1) * nrarb(n / 2) % MOD2;
  else
    rez = nrarb(n / 2) * nrarb(n / 2) % MOD2;
  n++;
  hrez[dr] = rez;
  hn[dr] = n;
  hnext[dr] = ult[n % MOD];
  ult[n % MOD] = dr;
  dr++;
  return rez;
}

int main(){
  FILE *in = fopen("ciuperci.in", "r");
  FILE *out = fopen("ciuperci.out", "w");
  int q, i, j;
  long long n;
  fscanf(in, "%d", &q);
  for(i = 0; i < q; i++){
    for(j = 0; j < MOD; j++){
      ult[j] = 0;
    }
    for(j = 0; j < 2 * LOGMAX + 1; j++){
       hnext[j] = hn[j] = hrez[j] = 0;
    }
    fscanf(in, "%lld", &n);
    dr = 1;
    fprintf(out, "%lld\n", nrarb(n));
  }
  fclose(in);
  fclose(out);
  return 0;
}