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

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

FILE *f = fopen("ciuperci.in","r");
FILE *g = fopen("ciuperci.out","w");

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

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

int LogRest(int li,int ls,ll N)
{
	if(li <= ls)
	{
		if(Log[(li+ls)/2] == N)
			return (li+ls)/2+1;
		else if(Log[(li+ls)/2] > N)
			return LogRest(li,(li+ls)/2-1,N);
		else
			return LogRest((li+ls)/2+1,ls,N);
	}
	return li;
}

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&1 ? 1:0, 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);
		return (1LL*2*A[depth][c]*A[depth][b])%Mod;
	}
	else
	{
		int b = a&1 ? 1:0;
		if(!A[depth][b])
			A[depth][b] = Tree(a/2,depth+1);
		return (1LL*A[depth][b]*A[depth][b])%Mod;
	}
}

int main()
{
	fscanf(f,"%d\n",&T);
	DOI();
	for(int i=1;i<=T;i++)
	{
		N = 0;
		fgets(S,sizeof(S),f);
		for(int j=0;isdigit(S[j]);j++)
			N = 1LL*N*10 + S[j]-'0';
		for(int i=1;i<=Depth;i++)
			A[i][0] = A[i][1] = A[i][2] = 0;
		Depth = LogRest(1,62,N);
		fprintf(g,"%d\n",Tree(N-Log[--Depth],1));
	}
	return 0;
}