#include <fstream>
#include <string>
#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;

string buffer;
string::iterator buffer_it;

void read_i64_nn( i64 &x ) {
    for ( ;*buffer_it<'0' || *buffer_it>'9'; ++buffer_it ) ;
    for ( x= 0; *buffer_it>='0' && *buffer_it<='9'; ++buffer_it ) {
        x= x*10+*buffer_it-'0';
    }
}

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 check( i64 x ) {
    int p= -1;
    for ( int i= 0; i<(int)v[x%modh].size() && p==-1; ++i ) {
        if ( v[x%modh][i].x==x ) {
            p= v[x%modh][i].y;
        }
    }

    return p;
}

int query( i64 x ) {
    if ( x<=1 ) return 1;
    int k= check(x);
    if ( k!=-1 ) return k;

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

int main(  ) {
    //getline( fin, buffer, (char)0 );
    //buffer_it= buffer.begin();

    i64 m;
    fin>>buffer; buffer_it= buffer.begin();
    read_i64_nn(m);
    for ( i64 cnt= 1; cnt<=m; ++cnt ) {
        i64 x;
        fin>>buffer; buffer_it= buffer.begin();
        read_i64_nn(x);

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

    return 0;
}