#include <cstdio>
#include <fstream>

using namespace std;

const int MOD = 666013;

int Q;
long long N;

long long power(int x, int y)
{
	if (y == 0) return 1;
	if (y % 2 == 0) return power((1LL * x * x) % MOD, y / 2);
	return (1LL * x * power((1LL * x * x) % MOD, y / 2)) % MOD;
}

int main()
{
	ifstream fin("ciuperci.in");
	ofstream fout("ciuperci.out");
	
	fin >> Q;
	while (Q--)
	{
		fin >> N;
		
		long long aux = 1;
		while (N >= aux)
			N -= aux, aux *= 2;
		
		long long result = 1, runda = aux, num1 = N, num2 = 0, exp1 = 1, exp2 = 0;
		if (N % 2 == 1)
		{
			swap(num1, num2);
			swap(exp1, exp2);
		}
		
		while (runda != 1)
		{
			if (num2 != 0)
				result *= power(2, exp2);
			result %= MOD;
			
			if (num1 != 0)
				num1 /= 2, exp1 *= 2;
			
			if (num1 == 0)
				num1 = num2 / 2, exp1 = 0;
			if (num1 != 0 && num2 != 0 && (num2 / 2 == num1 || num2 / 2 + 1 == num1))
				exp1 += exp2;
			if (num2 != 0 && num2 / 2 == num1) num2 = num2 / 2 + 1;
			else if (num2 != 0)
			{
				num2 = num2 / 2;
				if (num2 == 0) exp2 = 0;
			}
			
			if ((num1 == 0 && num2 % 2 == 0) || num1 % 2 == 1)
			{
				swap(num1, num2);
				swap(exp1, exp2);
			}
			
			runda /= 2;
		}
		
		fout << result << '\n';
	}
	
	fin.close();
	fout.close();
}