#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],Log[MaxN];

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

ll LogRest(ll N)
{
	for(Depth = 1;Log[Depth] < N;Depth++);
	return N-Log[--Depth];
}

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)
	{
		int b = a%2, c = b+1;
		if(!A[depth][c])
			A[depth][c] = Tree(a/2+1,depth+1);
		if(!A[depth][b])
			A[depth][b] = Tree(a/2,depth+1);
		ll inm = 1LL*2*A[depth][c]*A[depth][b];
		if(inm >= Mod)
			inm %= Mod;
		return inm;
	}
	else
	{
		int b = a%2;
		if(!A[depth][b])
			A[depth][b] = Tree(a/2,depth+1);
		ll inm = 1LL*A[depth][b]*A[depth][b];
		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<=Depth;i++)
			A[i][0] = A[i][1] = A[i][2] = 0;
		g << Tree(LogRest(N),1) << "\n";
	}
	return 0;
}