#include <stdio.h>
#define MOD 666013

long long count(long long n)
{
	long long x;
	if (n == 0 || n == 1)
		return 1;
	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("ciuperci.out", "w", stdout);
	long long N;
	int Q;
	scanf("%d", &Q);
	for ( ; Q; --Q) {
		scanf("%lld", &N);
		printf("%lld\n", count(N) % MOD);
	} 	
	return 0;
}