#include <cstdio>
#include <fstream>

using namespace std;

const int MOD = 666013;

int Q, pow2[80002];
long long N;

inline int dub(int x)
{
	return (1LL * x * x) % MOD;
}
int power(long long exp)
{
	if (exp <= 80000) return pow2[exp];
	if (exp % 2 == 0) return dub(power(exp / 2));
	return (2 * dub(power(exp / 2))) % MOD;
}

int main()
{
	ifstream fin("ciuperci.in");
	ofstream fout("ciuperci.out");
	
	pow2[0] = 1;
	for (int i = 1; i <= 80000; ++i)
	{
		pow2[i] = pow2[i - 1] * 2;
		if (pow2[i] >= MOD) pow2[i] -= MOD;
	}
	
	fin >> Q;
	while (Q--)
	{
		fin >> N;
		
		long long aux = 1;
		while (N >= aux)
			N -= aux, aux *= 2;
		
		long long total = 0, 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)
				total += exp2;
			
			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 << power(total) << '\n';
	}
	
	fin.close();
	fout.close();
}