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

 long long int calc(long long int x)
 {
	 if (x==1)
		 return 1;
	 if (x==2)
		 return 2;
	 if (x%2==1)
	 {
		 long long int y=(calc((x-1)/2))%mod;
		 return y*y;
	 }
	 else
		 return (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;
	
}