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

int q;
ll n;
map <ll, int> m;

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

int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	scanf("%d", &q);
	while (q--)
	{
		scanf("%lld", &n);
		solve(n);
		printf("%lld\n", m[n]);
		m.clear();
	}
}