#include <fstream>

using namespace std;

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

typedef long long ll;

int const MODULO = 666013;

ll solve(ll c) {
  if(c <= 1){
    return 1;
  }else if(c % 2 == 1){
    ll mult = solve((c - 1) / 2);
    return (mult * mult) % MODULO;
  }else {
    return ((solve((c - 2) / 2) * solve(c / 2)) * 2) % MODULO;
  }
}

int main() {

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