#include <stdio.h>
#include <ctype.h>

#define WANTED 666013
#define MOD 32768
#define Dragoste 4096
#define MAX_MAP 200

#define i64 long long int

typedef struct {
  i64 v, count;
  int next;
} cell;

i64 N, Q;

/** Reprezentarea tabelei hash unde vom retine valorile functiei bkt(N). **/
int buff;
int hash[MOD];
cell map[MAX_MAP];

/** Parsarea intrarii. **/
int ptr = Dragoste;
char c, in[Dragoste];

char getChar(FILE *f) {
  if (ptr == Dragoste) {
    fread(in, 1, Dragoste, f);
    ptr = 0;
  }
  return in[ptr++];
}

void freef(FILE *f, const char *arg, i64 *result) {
  *result = 0;
  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    *result = (*result << 3) + (*result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
}

i64 mod(i64 x) {
  return x % WANTED;
}

/** Initializeaza tabela hash. **/
void init() {
  int i;
  
  for (i = 1; i <= buff; i++) {
    hash[map[i].v % MOD] = 0;
  }
  buff = 0;
}

int find(i64 x) {
  int pos;
  i64 h = x % MOD;

  for (pos = hash[h]; (pos != 0) && (map[pos].v != x); pos = map[pos].next);
  return pos;
}

void insert(i64 x, i64 count) {
  i64 h = x % MOD;

  map[++buff].v = x;
  map[buff].count = count;
  map[buff].next = hash[h];
  hash[h] = buff;
}

i64 bkt(i64 N) {
  if (N <= 2) {
    return N;
  }
  
  i64 left, right, result;
  int pos = find(N);
  if (pos) {
    return map[pos].count;
  }

  /* Daca "N" este impar inseamna ca cei doi subarbori au acelasi numar de 
     noduri. */
  left = bkt(N / 2);
  if (N % 2) {
    result = mod((i64)left * left);
  } else {
    right = mod(bkt(N / 2 - 1));
    result = mod(2LL * left * right);
  }
  insert(N, result);
  return result;
}

int main(void) {
  FILE *f = fopen("ciuperci.in", "r");
  freopen("ciuperci.out", "w", stdout);

  /* Citirea datelor si afisarea solutiei. */
  for (freef(f, "%lld", &Q); Q; Q--) {
    freef(f, "%lld", &N);
    fprintf(stdout, "%lld\n", bkt(N));
    init();
  }
  fclose(f);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}