///   InfoArena ~~ Ciuperci

#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

typedef long long I64;

const int MOD  = 666013;
const int HMOD = 32;

struct DYN {
    int r;
    I64 v;
};

DYN make_DYN( int a, int b ) {
    DYN aux;
    aux.r = a;
    aux.v = b;
    return aux;
}

vector <DYN> Hash[HMOD];
int N,Q;

void init() {
    for( int i= 0;  i<HMOD;  ++i ) Hash[i].clear();
}

int Querry( int q ) {
    if( q < 3 ) return q;
    if( q == 3 ) return 1;

    int key = q % HMOD;
    I64 Ans;

    for( int i= 0;  i<(int)Hash[key].size();  ++i ) {
        if( q == Hash[key][i].v ) return Hash[key][i].r;
    }

    I64 Q1 = Querry(q/2);
    I64 Q2 = Querry(q/2+1);
    if( q%2 == 0 ) {
        Ans = (I64)(Q1*Q1) % MOD;
        Hash[key].push_back( make_DYN( Ans, q ) );
    }
    else {
        Ans = (I64)( ( (I64)(Q1*Q2) % MOD ) * 2 ) % MOD;
        Hash[key].push_back( make_DYN( Ans, q ) );
    }

    return Ans;
}

int main() {
    int T;
    in >> T;
    while( T-- ) {
        in >> Q;
        init();
        out << Querry(Q) << '\n';
    }
    return 0;
}