/**
  *  Worg
  */
#include <cstdio>
#include <unordered_map>

using namespace std;
FILE *fin = freopen("ciuperci.in", "r", stdin);
FILE *fout = freopen("ciuperci.out", "w", stdout);

const int bufferDim = 500;
const int P = 666013;

class inputReader {

private:
        char buffer[bufferDim];
        int pos = 0;

        bool digit(char c) {

            return('0' <= c && c <= '9');
        }
public:

        void getBuffer() {

            fread(buffer, 1, bufferDim, stdin);
            pos = 0;
        }

        void getLongLong(long long &nr) {

            nr = 0;
            while(!digit(buffer[pos]))
                if(++pos == bufferDim)
                    getBuffer();
            while(digit(buffer[pos])) {

                nr = nr * 10 + 1LL * (buffer[pos] - '0');
                if(++pos == bufferDim)
                    getBuffer();
            }
        }
} cin;

unordered_map <long long int, int> umap;

int back(long long int n) {

    if(umap[n]) {
        return umap[n];
    }
    else {
        n--;
        if(n % 2 == 0) {
            int k = back(n / 2);
            int answer = (1LL * k * k) % P;
            umap[n + 1] = answer;
            return answer;
        }
        else {
            int k1 = back(n / 2), k2 = back(n / 2 + 1);
            int answer = (2LL * k1 * k2) % P;
            umap[n + 1] = answer;
            return answer;
        }
    }
}

int main() {

    cin.getBuffer();
    umap[1] = 1;
    umap[2] = 2;

    long long q;
    for(cin.getLongLong(q); q > 0; --q) {
        long long n; cin.getLongLong(n);
        printf("%d\n", back(n));
    }

    return 0;
}