#include<cstdio>
using namespace std;
const long long MOD = 666013;
long long N,T;
long long solve(long long X){
	if(X==1)
		return 1;
	if(X==2)
		return 2;
	if(X&1){
		long long sol=solve(X>>1);
		return (sol*sol)%MOD;
	}
	return (solve((X-1)>>1)*solve(X>>1)*2)%MOD;
}
int main(){
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	scanf("%lld",&T);
	for(;T;--T){
		scanf("%lld",&N);
		printf("%lld\n",solve(N));
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}