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

using namespace std;

typedef long long ll;
const ll mod = 666013;

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

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