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

typedef long long ll;
const char *FIN = "ciuperci.in", *FOU = "ciuperci.out";
const int MOD = 666013, mod = 32, hg = 1 << 13;

int T, poz;
ll N;
char ch[hg];

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

# define foreach(vec) for (typeof (vec.begin ()) it = (vec).begin (); it != (vec).end (); ++it)
# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0

inline void cit (int &x) {
    int semn = 1;
    if (ch[0] == '\0') fread (ch, 1, hg, stdin) ;
    else for (; (ch[poz] < '0' || ch[poz] > '9') && ch[poz] != '-' ; verf) ;
    for (x = 0 ; (ch[poz] >= '0' && ch[poz] <= '9') || ch[poz] == '-' ; (ch[poz] == '-' ? semn = -1 : x = x * 10 + ch[poz] - '0'), verf) ;
    x *= semn;
}

inline void cit (ll &x) {
    int semn = 1;
    if (ch[0] == '\0') fread (ch, 1, hg, stdin) ;
    else for (; (ch[poz] < '0' || ch[poz] > '9') && ch[poz] != '-' ; verf) ;
    for (x = 0 ; (ch[poz] >= '0' && ch[poz] <= '9') || ch[poz] == '-' ; (ch[poz] == '-' ? semn = -1 : x = x * 10 + ch[poz] - '0'), verf) ;
    x *= semn;
}

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 (cit (T); T; --T) {
        for (int i = 0; i < mod; ++i) G[i].clear ();
        cit (N);
        printf ("%d\n", rez (N));
    }
}