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

}

ll solve1(ll c) {
  if(c <= 1){
    return 1;
  }else if(c % 2 == 1){
    ll multa = solve((c - 1) / 2), ans1 = multa * multa;
    if(ans1 >= MODULO){
      return ans1 % MODULO;
    }
    return ans1;
  }else {
    ll mult11 = solve(c / 2 - 1), mult21 = solve(c / 2), ans1 = (mult11 * mult21 * 2);
    if(mult11 * mult21 * 2 >= MODULO) {
      return ans1 % MODULO;
    }
    return ans1;
  }

}

int main() {

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