#include <stdio.h>
#include <algorithm>
#define ll long long
#define MOD 666013
#define NMAX 10005
#define f first
#define s second
using namespace std;
int t,r,act;
ll n,act2;
pair <ll,int> A[NMAX];
inline int find(ll n)
{
	int i;
	for (i=1; i<=r; i++)
		if (A[i].f==n)
			return A[i].s;
	return -1;
}
inline int calcul(ll n)
{
	if (n==0)
		return 1;
	if (n==1)
		return 1;
	act=find(n);
	if (act!=-1)
		return act;
	if (n % 2==1)
	{
		act2=calcul(n/2);
		act2=act2*act2;
		if (act2>=MOD)
			act2%=MOD;
		act=act2;
	}
	else
	{
		act2=calcul(n/2);
		act2*=calcul(n/2-1)*2;
		if (act2>=MOD)
			act2%=MOD;
		act=act2;
	}
	A[++r].f=n; A[r].s=act;
	return act;
}
int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	scanf("%d",&t);
	int teste=0;
	while (t--)
	{
		scanf("%lld",&n);
		teste++;
		printf("%d\n",calcul(n));
		if (teste==4)
			r=0;
	}
	return 0;
}