# include <fstream>
# include <iostream>
# define ll long long
# define P 666013
using namespace std;
ll p[100], n, q;

void pu ()
{
	p[0]=1;
	for(int i=1;i<63;++i)
		p[i]=p[i-1]*2;
}

void f ()
{
	q=1;
	while (p[q+1]-1<=n)++q;
	n-=p[q]-1;
	q=p[q-1];
}

ll calc (int unu, int doi, int q)
{
	if (unu==1 && !doi)
		return 2*q;
	if (doi==1 && !unu)
		return q;
	if (unu==1 && doi)
		return (2*(unu+doi))%P;
	if (doi==1 && unu)
		return (p[unu]%P*(unu+doi))%P;
	int u1=unu/2, u2=unu-u1, d1=doi/2, d2=doi-d1;
	if (u1!=u2 || d1!=d2)
		return (2*calc(u1, d1, q/2)*calc(u2, d2, q/2))%P;
	ll r=calc(u1, d1, q/2);
	return (r*r)%P;
}

int solve ()
{
	f();
//	cout<<n<<" "<<q<<" # ";
	int unu, doi;
	if (n<=q)unu=n, doi=0;
	else doi=n-q, unu=q-doi;
//	cout<<unu<<" "<<doi<<" "<<q<<endl;
	return calc(unu, doi, q);
}

int main ()
{
	pu();
	ifstream fin ("ciuperci.in");
	freopen("ciuperci.out", "w", stdout);
	int t;
	fin>>t;
	for(;t--;)
	{
		fin>>n;
		if (n==1)printf("1\n");
		else printf("%d\n", solve());
	}
	return 0;
}