///   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 = 9903;
 
struct DYN {
    int r;
    I64 v;
};
 
inline DYN make_DYN( int a, I64 b ) {
    DYN aux;
    aux.r = a;
    aux.v = b;
    return aux;
}
 
// vector <DYN> Hash[HMOD];
I64 N,Q;
 
// inline void init() {
//     for( int i= 0;  i<HMOD;  ++i ) Hash[i].clear();
// }
 
I64 Querry( I64 q ) {
    if( q < 3 ) return q;
 
    // 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);
 
    if( q%2 == 1 ) {
        Ans = (1LL*Q1*Q1) % MOD;
        // Hash[key].push_back( make_DYN( Ans, q ) );
        return Ans;
    }
    else {
        I64 Q2 = Querry(q/2-1);
        Ans = (1LL*Q1*Q2*2) % MOD;
        // Hash[key].push_back( make_DYN( Ans, q ) );
        return Ans;
    }
}
 
int main() {
    I64 T;
    in >> T;
    // init();
    while( T-- ) {
        in >> Q;
        out << Querry(Q) << '\n';
    }
    return 0;
}