#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 modh= 32;

struct str {
    i64 x;
    int y;
};

inline str mp( i64 x, int y ) {
    str sol;
    sol.x= x, sol.y= y;
    return sol;
}

vector <str> v[modh];

int query( i64 x ) {
    if ( x<=2 ) return x;
    int k= x%modh;
    for ( int i= 0; i<(int)v[k].size(); ++i ) {
        if ( v[k][i].x==x ) return v[k][i].y;
    }

    int val;
    if ( x%2==1 ) {
        val= (i64)query(x/2)*query(x/2)%mod;
    } else {
        val= (i64)query(x/2)*query(x/2-1)*2%mod;
    }
    v[k].push_back(mp(x, val));
    return val;
}

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

        for ( int i= 0; i<modh; ++i ) v[i].clear();
        fout<<query(x)<<"\n";
    }

    return 0;
}