#include <fstream>
#include <cassert>

using namespace std;

typedef long long ll;
const ll mod = 666013;

inline ll val (ll x) {
	ll pas;
	for (pas = 1; pas <= x + 1; pas <<= 1);
	return pas - x - 1;
}

ll nr (ll n) {
	if (n < 2)	return 1;
	-- n; //root out
	ll next = (n >> 1), t = nr (next);
	t = (t * t) % mod;
	if (n & 1) {
		t = (t * 2 * val (next)) % mod;
	}
	return t;
}

void unit_tests () {
	assert (val (9ll) == 6);
	assert (val (0ll) == 1ll);
	assert (val (1ll) == 2ll);
	assert (val (2ll) == 1ll);
	assert (val (3ll) == 4ll);
	assert (val (4ll) == 3ll);
	assert (val (7ll) == 8ll);
	assert (val (127ll) == 128ll);
	assert (val (128ll) == 127ll);
	assert (val (6ll) == 1ll);
	assert (nr (1ll) == 1ll);
	assert (nr (2ll) == 2ll);
	assert (nr (3ll) == 1ll);
	assert (nr (4ll) == 4ll);
	assert (nr (5ll) == 4ll);
	assert (nr (127ll) == 1ll);
}

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