#include <cstdio>
#include <cstring>

const int AMOD = 666013 - 1;
const int MOD = 666013;

const int HMAX = 100000;

int H[HMAX];

int logcount(long long n)
{
	if (n <= 1) return 0;
	
	if (n < HMAX && H[n] != -1)
		return H[n];
	
	long long ans;
	long long r = logcount(n >> 1);
	
	if (n & 1)
		ans = r << 1;
	else
	{
		long long q = logcount(n/2 - 1);
		ans = r + q + 1;
	}
	
	if (ans >= AMOD) ans -= AMOD;
	
	if (n < HMAX) H[n] = ans;
	
	return ans;
}

int p2(int n)
{
	int p = 2;
	long r = 1;
	while (n)
	{
		if (n & 1)
			r = (r * p) % MOD;
		
		p = (p*p) % MOD;
		n >>= 1;
	}
	
	return r;
}

int main()
{
	freopen("ciuperci.in", "r", stdin);
	freopen("ciuperci.out", "w", stdout);

	memset(H, -1, sizeof(H));

	int Q;
	scanf("%d", &Q);
	while (Q--)
	{
		long long n;
		scanf("%lld", &n);
		printf("%d\n", p2(logcount(n)));
	}
	
	return 0;
}