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

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

vector < pair < long long, int > > v[MOD2];
int nr;

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;
}

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

int calc(long long n)
{
	if(n==1 || n==0)
		return 1;
	if(n==2)
		return 2;
	int cnt;
	cnt=cauta(n);
	if(cnt!=-1)
		return cnt;
	if((n&1)==0) {
		long long k;
		int nr1,nr2,sol;
		k=(n-2)/2;
        nr1=calc(k);
        nr2=calc(k+1);
        sol=(2LL*nr1*nr2)%MOD;
		adauga(mp(n,sol));
		return sol;
	}
	int nr,sol;
	nr=calc((n-1)/2);
	sol=(1LL*nr*nr)%MOD;
	adauga(mp(n,sol));
	return sol;
}

int main ()
{
	int i,q,j;
	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';
		for(j=0;j<=MOD2-1;j++)
			v[j].clear();
	}
	f.close();
	g.close();
	return 0;
}