#include <fstream>
#include <vector>

using namespace std;

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

typedef long long i64;

const int mod= 666013;

struct str {
    int x, y;
};

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

vector <str> v[mod];

i64 check( i64 x ) {
    i64 p= -1;
    for ( i64 i= 0; i<(i64)v[x%mod].size() && p==-1; ++i ) {
        if ( v[x%mod][i].x==x ) {
            p= v[x%mod][i].y;
        }
    }

    return p;
}

i64 query( i64 x ) {
    i64 p1= check(x/2), p2;
    if ( p1==-1 ) {
        p1= query(x/2)%mod;
        v[x/2%mod].push_back(mp(x/2, p1));
    }

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

        return ((i64)p1*p2*2%mod)%mod;
    }
}

int main(  ) {
    v[0].push_back(mp(0, 1));
    v[1].push_back(mp(1, 1));

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

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

    return 0;
}