#include <cstdio>
#include <map>
using namespace std;
#define mod 666013
#define ll long long

map <ll, int> m;

inline int solve (ll n)
{
	if (n==1) return 1;
	if (n==2) return 2;
	if (m[n]) return m[n];
	ll x, y=n>>1;
	if (n&1)
	{
		x=solve(y);
		x=(x*x)%mod;
		m[n]=x;
		return x;
	} else
	{
		x=solve(y);
		y=solve(y-1);
		x=(2*x*y)%mod;
		m[n]=x;
		return x;
	}
}

int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	char s[18];
	int i, q;
	ll n;
	scanf("%d\n", &q);
	while (q--)
	{
		n=0;
		fgets(s, 18, stdin);
		for (i=0; s[i]>='0' && s[i]<='9'; i++) n=n*10+s[i]-'0';
		printf("%lld\n", solve(n));
		m.clear();
	}
}