#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 , log = 0;
		for(int i=1;1<<i<=N;i++) log++;
		for(;log;log>>=1)
		{
			if(log & 1)
				ans = (1LL* ans *x)%MOD , log--;
			x = (1LL * x*x)%MOD;
		}
		fout<<ans<<'\n';
	}

	return 0;
}