#include <fstream>

using namespace std;

#define MAX_N 100000

#define prim 666013

ifstream f("ciuperci.in");
ofstream g("ciuperci.out");

#define ll long long

ll n;

inline int inm(int x, long long p) {
    if (p == 0)
        return 1;
    if (p == 1)
        return x;

    int ans = inm(x, p / 2);
    ans = (1LL * ans * ans) % prim;
    if (p % 2 == 1)
        ans = (1LL * ans * x) % prim;

    return ans;
}

int solve(ll f, ll n, ll p, ll q) {
    //numarul de solutii este 2^f * n ^ p * (n - 1) ^ q

    if (n <= 3) {
        int v[4] = {0, 1, 2, 1};

        int ans = inm(2, f);
        ans = (1LL * ans * inm(v[n], p)) % prim;
        ans = (1LL * ans * inm(v[n - 1], q)) % prim;

        return ans;
    }

    if (n % 2 == 0) {
        ll newN = n / 2;
        ll newP = p;
        ll newQ = 2 * q + p;
        ll newF = f + p;

        return solve(newF, newN, newP, newQ);
    }
    else {
        ll newN = n / 2;
        ll newP = 2 * p + q;
        ll newQ = q;
        ll newF = f + q; 
    
        return solve(newF, newN, newP, newQ);
    }
}

int main() {

    int T;
    for (f >> T; T; T--) {
        f >> n;

        if (n == 1)
            g << 1 << "\n";
        else 
            g << solve(0, n, 1, 0) << "\n";
    }
    
    return 0;    
}