#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

const int kModulo = 666013;

//returns both solutions for n+1 and n
std::pair< long long, long long > Solve(long long n) {
	if (n == 1)
		return std::make_pair(2, 1);

	if (n == 2)
		return std::make_pair(1, 2);

	if (n & 1LL) {
		auto aux = Solve(n >> 1);
		std::pair< long long, long long > res;

		res.first = 2 * aux.first * aux.second % kModulo;
		res.second = aux.second * aux.second % kModulo;

		return res;
	}
	else {
		auto aux = Solve((n >> 1) - 1);
		std::pair< long long, long long > res;

		res.first = aux.first * aux.first % kModulo;
		res.second = 2 * aux.first * aux.second % kModulo;

		return res;
	}
}

int main() {
	std::ifstream inputFile("ciuperci.in");
	std::ofstream outputFile("ciuperci.out");

	int testCount;
	inputFile >> testCount;

	while (testCount--) {
		long long n;
		inputFile >> n;

		outputFile << Solve(n).second << '\n';
	}

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!