# include <fstream>
# define mod 666013
# define asd(x) x*x*1L
using namespace std;
ifstream f ("ciuperci.in");
ofstream g ("ciuperci.out");
long long int x;
int i,n;

 long long int calc(long long int x)
 {
	 if (x==0)
		 return 1;
	 return (x%2==1)? asd(calc((x-1)/2))%mod:(2*calc((x-1)/2)*calc (x/2))%mod;
 }


int main ()
{
	f>>n;
	for (i=1;i<=n;i++)
	{
		f>>x;
		g<<(calc (x))%mod<<"\n";
	}
	
	
	return 0;
	
}