#include<iostream>
#include<stdio.h>
#include<fstream>
#include<vector>
using namespace std;

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

vector < pair < long long, int > > v[MOD2];
int poz;
char buff[DIM];

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

void citeste(long long &numar)
{
	while(buff[poz]<'0' || buff[poz]>'9')
		if(++poz==DIM) {
			fread(buff,1,DIM,stdin);
			poz=0;
		}
	numar=0;
	while(buff[poz]>='0' && buff[poz]<='9') {
		numar=numar*10LL+buff[poz]-'0';
		if(++poz==DIM) {
			fread(buff,1,DIM,stdin);
			poz=0;
		}
	}
}

int main ()
{
	int i,j;
	long long n,q;
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	citeste(q);
	for(i=1;i<=q;i++) {
		citeste(n);
		printf("%d\n",calc(n));
		for(j=0;j<=MOD2-1;j++)
			v[j].clear();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}