#include <cstdio>

const int MOD = 666013;

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

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

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