#include <cstdio>
#include <iostream>

using namespace std;

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


LL S[105], doi[105];

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;
	
	scanf ("%lld", &Q);
	
	while (Q --)
	{
		LL n;
		
		scanf ("%lld", &n);
		
		int i;
		for (i = 1; n >= S[i]; ++ i);
		
		if (n == S[i - 1])
			printf ("1\n");
		else
			printf ("%lld\n", doi[i] % MOD);		
	}
	
	return 0;
}