#include<stdio.h>
#include<set>
#define mod 666013
#define mod2 250000
using namespace std;
FILE*f=fopen("ciuperci.in","r");
FILE*g=fopen("ciuperci.out","w");

int q,i;
long long x;
set< pair<long long,int> >S[mod2]; set< pair<long long,int> >::iterator itt;

int rec ( long long n ){
	if ( n == 1 )	return 1;
	if ( n == 2 )	return 2;
	int list = n % mod2;
	itt = S[list].lower_bound(make_pair(n,0));
	if ( itt->first == n )	return itt->second;
	
	if ( n & 1 ){
		int aux = rec(n/2);
		aux = (1LL * aux * aux) % mod;
		S[list].insert(make_pair(n,aux));
		return aux;
	}
	else{
		int aux1 = rec((n-1)/2);
		int aux2 = rec((n-1)/2+1);
		int aux = (1LL * 2 * aux1 * aux2) % mod;
		S[list].insert(make_pair(n,aux));
		return aux;
	}
}

int main () {
	
	fscanf(f,"%d",&q);
	for ( i = 1 ; i <= q ; ++i ){
		fscanf(f,"%lld",&x);
		fprintf(g,"%d\n",rec(x));
		for ( int j = 0 ; j < mod2 ; ++j )
			S[j].clear();
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}