#include <cstdio>

const int MOD = 666013;

/*
	x = T(n+1), y = T(n)
	T(n) = nr de arbori super-ech cu n noduri
*/
void calc(long long n, long long &x, long long &y)
{
	if (n == 0) { x = 1; y = 1;	return;	}
	else
	if (n == 1) { x = 2; y = 1; return; }
	else
	if ( n == 2) { x = 1; y = 2; return; }
	
	long long t, s;
	
	if (n & 1)
	{
		calc(n >> 1, t, s);
		x = (2 * t *s) % MOD;
		y = (s * s) % MOD;
	}
	else
	{
	    calc((n >> 1) - 1, t, s);
		x = (t * t) % MOD;
		y = (2 * t * s) % MOD; 
	}
}

int main()
{
	freopen("ciuperci.in", "r", stdin);
	freopen("ciuperci.out", "w", stdout);
	
	int Q;
	scanf("%d", &Q);
	while (Q--)
	{
		long long n, x, y;
		scanf("%lld", &n);
		calc(n, x, y);
		printf("%lld\n", y);
	}
	
	return 0;
}