#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 & (n - 1))) {
		return n;
	}
	if (! (n & (n + 1))) {
		return 1;
	}
	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;
		if (t1 >= mod) {
			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;
}