#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, mult1, mult2, ans;

ll solve(ll c) {
  if(c <= 1){
    return 1;
  }else if(c % 2 == 1){
    mult = solve((c - 1) / 2), ans = mult * mult;
    if(ans >= MODULO){
      return ans % MODULO;
    }
    return ans;
  }else {
    mult1 = solve(c / 2 - 1), mult2 = solve(c / 2), ans = (mult1 * mult2 * 2);
    if(mult1 * mult2 * 2 >= 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;
}