#include <fstream>
#include <cstring>
using namespace std;

#define MOD 666013
#define in "ciuperci.in"
#define out "ciuperci.out"
#define NMAX 100

long long states[NMAX],visited[NMAX];
int counnt = 0;

inline int isVisited(long long nr)
{
	int i,cnt = counnt;
	
	for(i = 1; i <= cnt; i++)
		if(visited[i] == nr)
			return i;
	return 0;
}

void calcul(long long N,int nr)
{
	int v1,v2;
	if(N == 1)
		{
			states[nr] = 1;
			return;
		}
	else
		if(N==2)
			{
				states[nr] = 2;
				return;
			}
	else
		if(N % 2 == 0)
		{
			v1 = isVisited(N/2);
			v2 = isVisited(N/2-1);
			if(!v2)
			{
				v2 = counnt + 1;
				visited[++counnt] = N/2 - 1;
				calcul(N/2 - 1,counnt);
				
			}
			if(!v1)
			{
				v1 = counnt + 1;
				visited[++counnt] = N/2;
				calcul(N/2,counnt);
				
			}
			states[nr] = states[v1] * 2;
			while(states[nr] >= MOD)
				states[nr]-=MOD;
			states[nr] *= states[v2];
			states[nr] %= MOD;
		}
		else
		{
			v1 = isVisited((N-1)/2);
			if(!v1)
			{
				v1 = counnt + 1;
				visited[++counnt] = (N-1)/2;
				calcul(N/2,counnt);
				
			}
			states[nr] = (states[v1] * states[v1]) % MOD;
		}
}

ifstream fin(in);
ofstream fout(out);

int main()
{
	int i,Q;
	long long n;
	
	char sir[20];
	int lg,j;
	fin>>Q;
	fin.get();
	
	for(i=1; i<=Q; i++)
		{
			fin.get(sir,20,'\n');
			fin.get();
			n = 0;
			lg = strlen(sir);
			for(j=0; j<lg; j++)
			{
				n*=10;
				n += sir[j] - '0';
			}
		
			visited[1] = n;
			counnt = 1;
			calcul(n,1);
			
			fout<<states[1]<<'\n';
		}
	
	return 0;
			
}