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

int q,i;
long long x;
vector< pair<long long,int> >H[32];

int rec ( long long n ){
	if ( n == 1 )	return 1;
	if ( n == 2 )	return 2;
	int list = n & (32 - 1);
	for ( vector< pair<long long,int> >::iterator itt = H[list].begin() ; itt != H[list].end() ; ++itt ){
		if ( itt->first == n ){
			return itt->second;
		}
	}
	if ( n & 1 ){
		int aux = rec(n/2);
		aux = (1LL * aux * aux) % mod;
		H[list].push_back(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;
		H[list].push_back(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));
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}