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

using namespace std;

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

typedef long long ll;

int const MODULO = 666013;

ll mult, mult2, ans;

ll solve(ll c) {
  if(c <= 1){
    return 1;
  }else if(c & 1 == 1){
    mult = solve((c - 1) >> 1);
    ans = mult * mult;
    if(ans >= MODULO){
      return ans % MODULO;
    }
    return ans;
  }else {
    ll mult1 = solve((c >> 1) - 1);
    mult2 = solve(c << 1);
    ans = (mult1 * mult2) << 1;
    if(ans >= MODULO) {
      return ans % MODULO;
    }
    return ans;
  }

}

int main() {

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