#include <fstream>
#include <vector>
#include<string>
using namespace std;
ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

struct ciuperca{
    long long x, y;
};

const int mod= 666013, auxmod = 63;
int q;
vector <ciuperca> h[auxmod];
string buffer;
string::iterator buffer_it;
 
int ciup(long long x) 
{
    if(x<3)
		return x;

    int rest = x % auxmod, chestie;
    for(int i = 0; i<(int)h[rest].size(); i++)
	{
        if(h[rest][i].x==x)
			return h[rest][i].y;
    }
 
    if(x%2==1) 
	{
        chestie = (long long)ciup(x / 2) * ciup(x / 2) % mod;
    }
	else
	{
        chestie = (long long)ciup(x / 2) * ciup(x / 2 - 1) * 2 % mod;
    }

	ciuperca aux;
	aux.x = x;
	aux.y = chestie;
    h[rest].push_back(aux);

    return chestie;
}

void read_int_nn( long long &x ) {
    for ( ; *buffer_it>'9' || *buffer_it<'0'; ++buffer_it ) ;
    for ( x= 0; *buffer_it>='0' && *buffer_it<='9'; ++buffer_it ) {
        x= x*10+*buffer_it-'0';
    }
}

int main(){
	int player_unu=0;
    in>>q;
	getline(in, buffer, (char)0);
    buffer_it = buffer.begin();
	
    for (int shp = 0; shp<q; shp++)
	{
        long long x;
        read_int_nn(x);
 
        for(int i = 0; i<auxmod; i++)
			h[i].clear();

        out<<ciup(x)<<"\n";
    }
 
    return player_unu;
}