#include <cstdio>

const int MOD = 666013;

const int HMAX = 32000;

int H[HMAX];

int count(long long n)
{
	if (n <= 1) return 1;
	
	
	if (n < HMAX && H[n])
		return H[n];
	
	long long ans;
	
	if (n & 1)
	{
		long long ret = count(n/2);
		ans = ret * ret % MOD;
	}
	else
	{
		long long r1 = count(n/2);
		long long r2 = count(n/2 - 1);
		ans = r1*r2*2%MOD;
	}
	
	if (n < HMAX)
		H[n] = ans;
	
	return ans;
}

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

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