# include <fstream>
# define mod 666013
# define m 1000000
using namespace std;
ifstream f ("ciuperci.in");
ofstream g ("ciuperci.out");
long long int x,w;
int i,n,a[m+10];
 long long int calc(long long int x)
 {
	 if (x==0)
		 return 1;

	 long long int q=(x-1)/2;
	 if (x%2==1)
	 {
		 if (q<=m && a[q]!=0)
			 return a[q]*a[q];
		 else
		 {
		 long long int y=calc(q)%mod;
		 return y*y;
		 }
	 }
	 else
		 if (q<m && a[q]!=0 && a[q+1]!=0)
			 return 2*a[q]*a[q+1];
			 else
		 return (2*calc(q)*calc (q+1))%mod;
	 
	 
 }


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