#include <stdio.h>

#define MAXN 60000
#define MOD 666013

int D[MAXN];
int T;
int i;
long long x;

int mem(long long x)
{
	if (x < MAXN) return D[x];
	
	int aux = mem(x/2);
	if (x % 2 == 1)
		return ((1LL * aux * aux) % MOD);
	else
		return ( (1LL * 2 * aux * mem(x/2 - 1) ) % MOD);
}

int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	
	scanf("%d",&T);
	D[0] = D[1] = 1;
	for (i=2; i<MAXN; ++i)
		if (i % 2 == 1)
			D[i] = (1LL * D[i/2] * D[i/2]) % MOD;
		else
			D[i] = (1LL * 2 * D[i/2] * D[i/2 - 1] ) % MOD; 
	
	for (i=1; i<=T; ++i){
		scanf("%lld\n",&x);
		printf("%d\n", mem(x));
	}
	
	return 0;
}