#include <cstdio>
#include <cstring>

const int MOD = 666013 - 1;

const int HMAX = 100000;

int H[HMAX], p2[MOD];

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 >= MOD) ans -=MOD;
	
	if (n < HMAX) H[n] = ans;
	
	return ans;
}

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

	p2[0] = 1;
	for (int i = 1; i< MOD; ++i)
	{
		p2[i] = p2[i-1] << 1;
		if (p2[i] >= MOD) p2[i] -= MOD;
	}
	
	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;
}