#include<stdio.h>
#include<fstream>
using namespace std;

#define ll long long
#define Mod 666013
#define MaxN 320
#define MaxP 5

ifstream f("ciuperci.in");
ofstream g("ciuperci.out");

int T,Depth,Doi[MaxN];
ll N,A[MaxN][MaxP];

void DOI(void)
{
	Doi[0] = 2;
	for(int i=1;i<=200;i++)
		Doi[i] = (Doi[i-1]*2)%Mod;
}

ll LogRest(ll N)
{
	ll a = 1, b = 1; Depth = 1;
	while(b + a * 2 * 1LL < N)
		a *= 2, b += a, Depth ++;
	return N-b;
}

int Tree(ll a,int depth)
{
	if(a == 0)
		return 1;
	else if(a == 2 && depth == Depth)
		return 1;
	else if(a == 1)
		return Doi[Depth-depth];
	if(a&1)
	{
		if(!A[depth][a%2+1])
			A[depth][a%2+1] = Tree(a/2+1,depth+1);
		if(!A[depth][a%2])
			A[depth][a%2] = Tree(a/2,depth+1);
		ll inm = 1LL*2*A[depth][a%2+1]*A[depth][a%2];
		if(inm >= Mod)
			inm %= Mod;
		return inm;
	}
	else
	{
		if(!A[depth][a%2])
			A[depth][a%2] = Tree(a/2,depth+1);
		ll inm = 1LL*A[depth][a%2]*A[depth][a%2];
		if(inm >= Mod)
			inm %= Mod;
		return inm;
	}
}

int main()
{
	f >> T;
	DOI();
	for(int i=1;i<=T;i++)
	{
		f >> N;
		for(int i=1;i<=200;i++)
			A[i][0] = A[i][1] = A[i][2] = 0;
		g << Tree(LogRest(N),1) << "\n";
	}
	return 0;
}