#include <fstream>

using namespace std;

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

const int MOD = 666013;

int t;
long long n;

int solve(long long n) {
  if(n <= 1)
    return 1;
  if(n & 1)
    return 1LL * solve(n / 2) * solve(n / 2) % MOD;
  return 2LL * solve(n / 2) * solve(n / 2 - 1) % MOD;
}

int main() {
  cin >> t;
  for(; t; t--) {
    cin >> n;
    cout << solve(n) << "\n";
  }
  return 0;
}