#include<bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;
long long  n, Q;

void func(long long n, long long &a, long long &b){
  if(n == 0) {a = 1; b = 1; return;}
  if(n == 1) {a = 2; b = 1; return;}
  if(n == 2) {a = 1; b = 2; return;}
  long long x, y;
  if(n & 1) {
    func(n / 2, x, y); a = 2 * x * y % MOD; b = y * y % MOD;
  }
  else {
    func(n / 2 - 1, x, y); a = x * x % MOD; b = 2 * x * y % MOD;
  }
}
int main()
{
  fin >> Q;
  while(Q--) {
    fin >> n;
    long long a, b;
    func(n, a, b);
    fout << b << "\n";
  }
  return 0;
}