#include <fstream>

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, pas;
		n --;
		t2 = nr (n >> 1ll);
		t1 = (t2 * t2) % mod;
		t1 <<= 1ll;
		if (t1 >= mod) {
			t1 -= mod;
		}
		for (pas = 1; n - (pas << 1) > 0; pas <<= 1);
		t1 *= ((pas << 1) - n);
		t1 = t1 & mod;
		return t1;
	}
}

int main () {
	int i, q;
	ll n;
	ifstream f ("ciuperci.in");
	ofstream g ("ciuperci.out");
	f >> q;
	while (q --) {
		f >> n;
		g << nr (n) << '\n';
	}
	f.close ();
	g.close ();
	return 0;
}