#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

#define MOD 666013
#define MOD2 1049
#define DIM 10001
#define mp make_pair
#define pb push_back
typedef pair < long long, int > PLLI;

//vector < pair < long long, int > > v[MOD];

/*
inline void adauga(PLLI x)
{
	v[x.first%MOD2].pb(x);
}

inline int cauta(long long x)
{
	int k;
	k=x%MOD2;
	for(vector <PLLI> :: iterator it=v[k].begin();it!=v[k].end();it++)
		if(it->first == x)
			return it->second;
	return -1;
}*/

int v[DIM];

int calc(long long n)
{
	if(n==1 || n==0)
		return 1;
	if(n<=DIM-1 && v[n])
		return v[n];
	if((n&1)==0) {
		long long k;
		int nr,sol;
		k=(n-2)/2;
		nr=calc(k);
		sol=(2LL*nr*nr)%MOD;
		if(n<=DIM-1)
			v[n]=sol;
		return sol;
	}
	int nr,sol;
	nr=calc((n-1)/2);
	sol=(1LL*nr*nr)%MOD;
	if(n<=DIM-1)
		v[n]=sol;
	return sol;
}

int main ()
{
	int i,q;
	long long n;
	ifstream f("ciuperci.in");
	ofstream g("ciuperci.out");
	f>>q;
	for(i=1;i<=q;i++) {
		f>>n;
		g<<calc(n)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}