#include <fstream>

using namespace std;

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

typedef long long i64;

const int mod= 666013;

i64 query( i64 x ) {
    if ( x<=1 ) return 1;
    
    if ( x%2==1 ) 
        return ((i64)query(x/2)%mod*query(x/2)%mod)%mod;
    return ((i64)2*query(x/2)%mod*query(x/2-1)%mod)%mod;
}

int main(  ) {
    i64 m;
    fin>>m;
    for ( i64 i= 1; i<=m; ++i ) {
        i64 x;
        fin>>x;

        fout<<query(x)<<"\n";
    }

    return 0;
}