#include<fstream>
#include<math.h>
#define MOD 666013
using namespace std;
ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

int testNr;
long long nodesNr;

long long trees(long long obj, long long boxes)
{
	//out<<obj<<" "<<boxes<<'\n';
	
	if(obj == 1)
		return boxes;
	else
	{	
		long long nr1, nr2, s;
		int mid = obj/2;

		nr1 = trees(mid, boxes/2);

		if(obj % 2 == 0)
		{	
			s = nr1*nr1;
			if(s > MOD)
				s %= MOD;
		}
		else 
		{	
			nr2 = trees(mid+1, boxes/2);	
			s = 2*nr1*nr2;
			if(s > MOD)
				s %= MOD;
		}
		return s;
	}
}



int main()
{	
	in>>testNr;
	
	for(;testNr; testNr--)
	{	
		in>>nodesNr;
		
		int logr = log2(nodesNr);
		
		long long dif = nodesNr - pow(2,(double)logr)+1;
		
		out<<trees(dif, pow(2, (double)logr))<<'\n';
		
	}
	in.close();
	out.close();
	return 0;
}