#include <fstream>
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] = ((2 * (states[v1] % MOD)) %MOD * states[v2] % MOD)%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] % MOD * states[v1] % MOD) % MOD;
		}
}

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

int main()
{
	int i,Q;
	long long n;
	
	fin>>Q;
	
	for(i=1; i<=Q; i++)
		{
			fin>>n;
			visited[1] = n;
			counnt = 1;
			calcul(n,1);
			fout<<states[1]<<'\n';
		}
	
	return 0;
			
}