#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;

unordered_map <long long, int> ans;

int solve(long long n) {
  if(ans.find(n) != ans.end())
    return ans[n];
  if(n & 1)
    ans[n] = 1LL * solve(n / 2) * solve(n / 2) % MOD;
  else
    ans[n] = 2LL * solve(n / 2) * solve(n / 2 - 1) % MOD;
  return ans[n];
}

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