#include <stdio.h>

#define MOD 666013
#define MAXLOG 60

long long Aux, N, Ans, putere, K;
int T;
int i, nr, x;
long long put2[MAXLOG];

int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	
	scanf("%d",&T);
	
	put2[0] = 1LL;
	for (i=1; i<MAXLOG; ++i)
		put2[i] = put2[i-1] * 2;
	
	for (; T; --T){
		scanf("%lld",&N);
		
		Aux = 1LL; nr = 0;
		while (Aux <= N){
			N-= Aux;
			Aux = Aux*2;
			++nr;
		}
		
		K = N; N = nr;
		putere = 0;

		while (K!=0 && N!=0){
			
			Aux = K-1;
			x = 0;
			while (Aux){
				++x;
				Aux = Aux / 2;
			}
			
			putere = putere + (N-x)*K;
			
			N = x;
			K = put2[N] - K;
		}
		
		Ans = 1;
		Aux = 2;
		for (i = 0; put2[i] <= putere; ++i){
			if (putere & put2[i])
				Ans = (Ans * Aux) % MOD;
			Aux = (Aux * Aux) % MOD;
		}
		
		printf("%d\n", Ans);
	}
	
	return 0;
}