///   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, I64 b ) {
    DYN aux;
    aux.r = a;
    aux.v = b;
    return aux;
}

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

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

int Querry( I64 q ) {
    if( q <= 2 ) return q;

    int key = q % HMOD;
    int Ans;

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

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

    return Ans;
}

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