#include <fstream>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

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

typedef long long ll;

int const MODULO = 666013;

vector <pair<ll, int>> sol[32];

inline int searchSol(int c, int group) {
  for(int i = 0;i < sol[group].size();i++){
    if(sol[group][i].first == c){
      return i;
    }
  }
  return -1;
}

ll solve(ll c) {

  if(c == 1){
    return 1;
  }else if(c == 2) {
    return 2;
  }

  int group = c & 31;
  int it = searchSol(c, group);

  if(it != -1){
    return sol[group][it].second;
  }else {
    ll ans = 0;
    if(c & 1 == 1){
      ll mult = solve((c - 1) >> 1);
      ans = (mult * mult) % MODULO;
    }else {
      ans = ((solve((c >> 1) - 1) * solve(c >> 1)) << 1) % MODULO;
    }
    sol[group].push_back({c, ans});
    return ans;
  }

}

int main() {

  int n;
  in >> n;
  for(int i = 1;i <= n;i++){
    ll c;
    in >> c;
    out << solve(c) << '\n';
    for(int j = 0;j <= 31;j++){
      sol[j].clear();
    }
  }
  return 0;
}