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

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

unordered_map < long long, int > v;
int poz;
char buff[DIM];

int calc(long long n)
{
	if(n==1 || n==0)
		return 1;
	if(n==2)
		return 2;
	if(v[n])
		return v[n];
	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;
		v[n]=sol;
		return sol;
	}
	int nr,sol;
	nr=calc((n-1)/2);
	sol=(1LL*nr*nr)%MOD;
	v[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;
	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));
		v.clear();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}