#include<bits/stdc++.h>


using namespace std;

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

const int MOD = 666013;
map<long long, pair<long long, long long>>mp;
int n, Q;

void func(long long n){
  if(n == 0) {mp[n] = {1, 1}; return;}
  if(n == 1) {mp[n] = {2, 1}; return;}
  if(n == 2) {mp[n] = {1, 2}; return;}
  if(n & 1) {
    func(n / 2); mp[n].first = 2 * mp[n / 2].first * mp[n / 2].second % MOD; mp[n].second = mp[n / 2].second * mp[n / 2].second % MOD;
  }
  else {
    func(n / 2 - 1); mp[n].first = mp[n / 2 - 1].first * mp[n / 2 - 1].first % MOD; mp[n].second = 2 * mp[n / 2 - 1].first * mp[n / 2 - 1].second % MOD;
  }
}
int main()
{
  fin >> Q;
  while(Q--) {
    fin >> n;
    func(n);
    fout << mp[n].second << "\n";
  }
  return 0;
}