#include <stdio.h>
#define MOD 666013
#define NMAX 100000

long long prec[NMAX];

void precalc()
{
	long long i;
	prec[0] = prec[1] = 1;
	for (i = 2; i < NMAX - 1; ++i)
		if (i % 2 == 0)
			prec[i] = (2 * prec[i / 2] * prec[i / 2 - 1]) % MOD;
		else
			prec[i] = (prec[i / 2] * prec[i / 2]) % MOD;
}
			
long long count(long long n)
{
	long long x;
	if (n < NMAX - 1)
		return prec[n];
	if (n % 2 == 0)
		return (2 * count(n/2) % MOD) * (count(n/2 - 1) % MOD);
	else {
		x = count(n / 2);
		return (x % MOD) * (x % MOD);
	}
}

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

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