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

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

void solve (ll n, ll p, ll &r1, ll &r2)
{
	ll a, b;
	if (n==1) 
	{
		r1=1;
		r2=2;
		return;
	}
	if (n==2) 
	{
		r1=2;
		r2=1;
		return;
	}
	if (m[n] && m[p]) return;
	ll x, y=n/2;
	if (n&1)
	{
		x=n/2;
		y=x+1;
		solve(x, y, a, b);
		r1=(a*a)%mod;
		r2=(2*a*b)%mod;
	} else
	{
		x=n/2-1;
		y=x+1;
		solve(x, y, a, b);
		r1=(2*a*b)%mod;
		r2=(b*b)%mod;
	}
	m[n]=r1;
	m[p]=r2;
	
}

int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	scanf("%d", &q);
	ll a, b;
	while (q--)
	{
		scanf("%lld", &n);
		h=0;
		solve(n, n+1, a, b);
		printf("%lld\n", a);
		m.clear();
	}
}