#include <map>
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
map <ll, ll> bbt;
const ll mod = 666013;

ll nr (ll n) {
	if (bbt [n]) {
		return bbt [n];
	}
	if (n & 1) {
		ll t = nr (n >> 1ll);
		t = (t * t) % mod;
		bbt [n >> 1ll] = t;
		return t;
	}
	else {
		ll t1, t2;
		t1 = nr (n >> 1ll);
		bbt [n >> 1ll] = t1;
		n --;
		t2 = nr (n >> 1ll);
		bbt [n >> 1ll] = t2;
		t1 = (t1 * t2) % mod;
		t1 <<= 1ll;
		t1 = t1 % mod;
		return t1;
	}
}

int main () {
	int i, q;
	ll n;
	bbt [1] = 1;
	bbt [2] = 2;
	freopen ("ciuperci.in", "rt", stdin);
	freopen ("ciuperci.out", "wt", stdout);
	cin >> q;
	while (q --) {
	cin >> n;
	cout << nr (n) << '\n';
	}
	return 0;
}