///   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;

struct DYN {
    I64 r;
    I64 v;
};

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

vector <DYN> Hash[MOD+1];
I64 N,Q;

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

    I64 key = q % MOD;
    I64 Ans;

    for( I64 i= 0;  i<(I64)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 == 0 ) {
        Ans = (Q1*Q1) % MOD;
        Hash[key].push_back( make_DYN( Ans, q ) );
    }
    else {
        Ans = ( ( (Q1*Q2) % MOD ) * 2 ) % MOD;
        Hash[key].push_back( make_DYN( Ans, q ) );
    }

    return Ans;
}

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