#include <cstdio>
#include <iostream>

using namespace std;

#define LL long long
#define maxFact 1050
#define MOD 666013


LL S[105], doi[105];
LL fact[maxFact];


int power (int A, int N)
{
	if ( ! N ) return 1;
	
	LL halfpower = power (A, N / 2);
	
	if (N % 2) return (((halfpower * halfpower) % MOD) * A) % MOD;
	else return (halfpower * halfpower) % MOD;
}


void factorial (int N)
{
	fact[1] = 1;
	
	for (int i = 2; i <= N; ++ i) fact[i] = (fact[i - 1] * i) % MOD;		
}



inline int Comb (int N, int K)
{
	if (N == K) return 1;
	if ( ! K ) return 1;
	
	LL N_K =  power ( fact[N - K], MOD - 2 );
	LL K_fact = power ( fact[K], MOD - 2 );
	
	return (((fact[N] * N_K) % MOD) * K_fact) % MOD;
}


int main()
{
	freopen ("ciuperci.in", "r", stdin);
	freopen ("ciuperci.out", "w", stdout);
	
	doi[1] = 1;
	S[1] = 1;
	
	LL lim = 1;
	
	for (int i = 1; i <= 16; ++ i)
		lim *= 10;
	
	for (LL i = 2; S[i - 1] <= lim; ++ i)
	{
		doi[i] = doi[i - 1] * 2;
		S[i] = S[i - 1] + doi[i];
	}
	
	LL Q;
	
	factorial (maxFact - 7);
	
	scanf ("%lld", &Q);
	
	while (Q --)
	{
		LL n;
		
		scanf ("%lld", &n);
		
		int i;
		for (i = 1; n >= S[i]; ++ i);
		
		LL rest = n - S[i - 1];
		
		if ( ! (rest % 2) )
		{
			LL C = Comb (doi[i - 1], rest / 2);
			printf ("%lld\n", (C * C) % MOD);
		}
		else
		{
			LL C1 = Comb (doi[i - 1], rest / 2);
			LL C2 = Comb (doi[i - 1], rest / 2 + 1);
			
			printf ("%lld\n", (2 * C1 * C2) % MOD);
		}
	}
	
	
	
	return 0;
}