#include <bits/stdc++.h>

using namespace std;

const int mod = 666013;

map<int64_t, int>cnt;

int nr(int64_t n) {
	if (n == 1)
		return 1;

	if (n == 0)
		return 1;

	if (cnt.find(n) != end(cnt))
		return cnt[n];

	if (n % 2)
		return cnt[n] = (1LL * nr(n / 2) * nr(n / 2)) % mod;

	int v1 = nr(n / 2), v2 = nr(n / 2 - 1);
	return cnt[n] = (2LL * v1 * v2) % mod;
}

int32_t main() {
	ifstream cin("ciuperci.in");
	ofstream cout("ciuperci.out");

	int t;
	cin >> t;

	while (t--) {
		int64_t n;
		cin >> n;
		cnt.clear();
		cout << nr(n) << '\n';
	}
}