#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

#define LL long long
#define MOD 666013

int complex;

LL compute(LL n)
{
	LL ans;
	++complex;
	if (n == 0) return 1; 
	if (n % 2) 
	{
		LL half = compute((n-1)/2);
		ans = (half*half)%MOD;
	}	
	else
	{
		LL val1 = compute((n-1)/2+1);
		LL val2 = compute((n-1)/2);
		ans = (2*val1*val2)%MOD;
	}	
	return ans;
}

int main()
{
	freopen ("ciuperci.in", "r", stdin);
	freopen ("ciuperci.out", "w", stdout);
	
	int Q;
	scanf ("%d", &Q);
	
	while (Q--)
	{
		LL N;
		scanf("%lld", &N);
		complex = 0;
		printf ("%lld\n", compute(N));
	}	
	
	return 0;
}