#include <bits/stdc++.h>

using namespace std;

ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");

/// f(x) - numarul de arbori diferiti ce respecta conditia din enunt care au x noduri
/// Cazul 1: x - impar
///          considerand radacina, obtinem ca subarborii fiilor trebuie sa aiba acelasi numar de noduri
///          (x - 1) / 2, deci f(x) = (f(x - 1) / 2) ^ 2
///          1(radacina) + (x - 1) / 2 + (x - 1) / 2 = x
/// Cazul 2: x - par
///          procedand analog anterior, f(x) = (f(x / 2 - 1) * f(x / 2) * 2
///          1(radacina) + (x / 2 - 1) + x / 2 = x
///          se inumulteste cu 2 pentru ca fiecare dintre cele 2 size-uri diferite poate fi in stanga sau in dreapta
/// a = f(x + 1)
/// b = f(x)

const int mod = 666013;

void f(int64_t x, int &a, int &b) {
  if (x == 0) {
    a = b = 1;
    return;
  }
  if (x == 1) {
    a = 2;
    b = 1;
    return;
  }
  int _a, _b;
  if (x & 1) {
    f(x >> 1, _a, _b);
    a = (int64_t)_a * _b * 2 % mod;
    b = (int64_t)_b * _b % mod;
  } else {
    f((x >> 1) - 1, _a, _b);
    a = (int64_t)_a * _a % mod;
    b = (int64_t)_a * _b * 2 % mod;
  }
}

void test_case() {
  int Q;
  fin >> Q;
  for (int i = 1; i <= Q; ++i) {
    int64_t x;
    fin >> x;
    int a, b;
    f(x, a, b);
    fout << b << '\n';
  }
}

int main() {
  int t = 1;
  for (int tc = 1; tc <= t; ++tc) {
    test_case();
  }
  fin.close();
  fout.close();
  return 0;
}