#include <fstream>
#include <unordered_map>

using namespace std;

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

const int MOD = 666013;

int t;
long long n, a, b;

void solve(long long n, long long &a, long long &b) {
  if(n == 0) {
    a = b = 1;
    return;
  }
  if(n == 1) {
    a = 2, b = 1;
    return;
  }
  if(n == 2) {
    a = 1, b = 2;
    return;
  }
  long long a_, b_;
  if(n & 1) {
    solve(n / 2, a_, b_);
    a = 2LL * a_ * b_ % MOD;
    b = 1LL * b_ * b_ % MOD;
  } else {
    solve(n / 2 - 1, a_, b_);
    a = 1LL * a_ * a_ % MOD;
    b = 2LL * a_ * b_ % MOD;
  }
}

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