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

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

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

ll pow(ll n, ll p)
{
	ll r=1;
	int i;
	for (i=1; i<=p; i<<=1)
	{
		if (i&p) r=(r*n)%mod;
		n=n*n%mod;
	}
	return r;
}

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