#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define mp make_pair
const int mod = 666013;
const int h = 9007;
using namespace std;

vector < pair<ll , int> > H[h];

int i , j , t , cnt , mem[100005];
ll a;

int hash_look ( ll a ) {
	
	int i;
	int p = a % h;
	
	for ( i = 0 ; i < H[p].size() ; ++i )
		if ( H[p][i].first == a )
			return H[p][i].second;
		
return -1;
}

int ret ( ll a ) {
	
	if (a <= 100000) return mem[a];
	int p = hash_look(a);
	if ( p != -1 ) return p;
	
	cnt++;
	
	if ( a & 1 ) {
		int ans = ret ( a >> 1 );
		ans = (1LL * ans * ans) % mod;
		H[a % h].pb( mp(a , ans));
		return ans;
	}
	
	int ans1 = ret ( a >> 1 ) , ans2 = ret((a >> 1) - 1);
	
	ans1 = (2LL * ans1 * ans2) % mod;
	H[a % h].pb( mp (a , ans1));
	return ans1;
}

int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	
	scanf("%d",&t);
	
	mem[1] = 1 , mem[2] = 2;
	
	for ( i = 3 ; i <= 100000; ++i )
		if ( i & 1 )
			mem[i] = 1LL * mem[i >> 1] * mem[i >> 1] % mod;
		else
			mem[i] = 2LL * mem[i >> 1] * mem[(i >> 1) - 1] % mod;
	
	for ( i = 1 ; i <= t ; ++i ) {
		scanf("%lld",&a);
		printf("%d\n",ret(a));
		if ( cnt > 30000 ) {
			for ( j = 0 ; j < 9007 ; ++j )
				H[j].clear();
			cnt -= 30000;
		}
		
		//printf("%d\n",cnt);
	}
	
	//printf("%d\n",cnt);
	
return 0;
}