#include <fstream>
#include <map>

using namespace std;

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

typedef long long ll;

int const MODULO = 666013;

map <ll, int> sol;

ll solve(ll c) {
  auto it = sol.find(c);
  if(it != sol.end()){
    return it->second;
  }else {
    ll ans = 0;
    if(c <= 1){
      ans = 1;
    }else if(c % 2 == 1){
      ll mult = solve((c - 1) / 2);
      ans = (mult * mult) % MODULO;
    }else {
      ll mult1 = solve(c / 2 - 1), mult2 = solve(c / 2);
      ans = (mult1 * mult2 * 2) % MODULO;
    }
    sol[c] = ans;
    return ans;
  }

}

int main() {

  int n;
  in >> n;
  for(int i = 1;i <= n;i++){
    int c;
    in >> c;
    out << solve(c) << '\n';
  }
  return 0;
}