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

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

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

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

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

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

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

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