# include <cstdio>
# include <vector>
using namespace std;

typedef long long ll;
const char *FIN = "ciuperci.in", *FOU = "ciuperci.out";
const int MOD = 666013, mod = 37;

int T;
ll N;

vector < pair <ll, int> > G[mod];

# define foreach(vec) for (typeof (vec.begin ()) it = (vec).begin (); it != (vec).end (); ++it)

inline int find (ll x) {
    int val = x % mod;

    foreach (G[val])
        if (it -> first == x)
            return it -> second;
    return -1;
}

inline void insert (ll x, int VAL) {
    int val = x % mod;
    G[val].push_back (make_pair (x, VAL));
}

int rez (ll N) {
    if (N == 0 || N == 1) return 1;
    int x = find (N);
    if (x != -1) return x;
    int aux = rez (N >> 1);
    if (N & 1)
        aux = (1LL * aux * aux) % MOD;
    else aux = (1LL * aux * rez ((N >> 1) - 1) << 1) % MOD;
    insert (N, aux);
    return aux;
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    for (scanf ("%d", &T); T; --T) {
        for (int i = 0; i < mod; ++i) G[i].clear ();
        scanf ("%lld", &N);
        printf ("%d\n", rez (N));
    }
}