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

int q,i;
long long x;
map<long long,int>M;

int rec ( long long n ){
	if ( n == 1 )	return 1;
	if ( n == 2 )	return 2;
	int x = M[n];
	if ( x ){
		if ( x < 0 )	return 1;
		return x;
	}
	if ( n & 1 ){
		int aux = rec(n/2);
		aux = (1LL * aux * aux) % mod;
		M[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;
		M[n] = aux;
		return aux;
	}
}

int main () {
	
	fscanf(f,"%d",&q);
	for ( long long p = 1 ; p <= 10000000000000000LL ; p *= 2 ){
		M[p-1] = -1;
	}
	for ( i = 1 ; i <= q ; ++i ){
		fscanf(f,"%lld",&x);
		fprintf(g,"%d\n",rec(x));
		if ( M.size() > 200000 ){
			for ( map<long long,int>::iterator itt ; itt != M.end() ; ++itt ){
				if ( itt->second > 0 )
					M.erase(itt);
			}
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}