#include<fstream>
#include<vector>

using namespace std;

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

typedef long long i64;

const int mod = 666013;
const int hmod = 32;
struct str{ i64 k; int d; };
vector <str> h[ hmod ];

inline str mp( i64 k, int d ) {
    str sol;
    sol.k = k; sol.d = d;
    return sol;
}
int find_d( i64 k ) {
    int key = k % hmod;
    for( int i = 0; i < ( int )h[ key ].size(); ++ i ) {
        if ( h[ key ][ i ].k == k ) {
            return h[ key ][ i ].d;
        }
    }
    return -1;
}
i64 solve( i64 n ) {
    i64 y, x = find_d( n );
    if ( x != -1 ) {
        return x;
    }
    i64 k = n / 2;
    if ( n % 2 == 0 ) {
        y = 2 * solve( k ) * ( i64 )solve( k - 1 );
        y %= mod;
        h[ n % hmod ].push_back( mp( n, y ) );
        return y;
    } else {
        y = solve( k );
        y *= y;
        y %= mod;
        h[ n % hmod ].push_back( mp( n, y ) );
        return y;
    }
}
int main() {
    int t; long long x;
    fin >> t;
    while ( t -- ) {
        h[ 1 ].push_back( mp( 1, 1 ) );
        h[ 2 ].push_back( mp( 2, 2 ) );
        fin >> x;
        fout << solve( x ) << "\n";
        for( int i = 0; i < hmod; ++ i ) {
            h[ i ].clear();
        }
    }
    fin.close();
    fout.close();
    return 0;
}