#include <fstream>

using namespace std;

ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");

const int MOD = 666013;

int main()
{
	int Q , N ;
	for(fin>>Q;Q;Q--)
	{
		fin>>N;
		int ans = 1 , x = 2 , log2 = 0;
		for(int i=1;(1<<i)<=N;i++) log2++;
		for(;log2;log2>>=1)
		{
			if(log2 & 1)
				ans = (1LL* ans *x)%MOD , log2--;
			x = (1LL * x*x)%MOD;
		}
		fout<<ans<<'\n';
	}

	return 0;
}