#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

const int MOD = 666013;
const int MAXN = 100000;  // The maximum number of nodes we will precompute for

vector<long long> dp(MAXN + 1, 0);

void precompute() {
    dp[0] = dp[1] = 1;  // Base cases

    for (int i = 2; i <= MAXN; ++i) {
        for (int k = 0; k <= i - 1; ++k) {
            int left = k;
            int right = i - 1 - k;
            if (abs(left - right) <= 1) {
                dp[i] = (dp[i] + dp[left] * dp[right]) % MOD;
            }
        }
    }
}

int main() {
    ifstream infile("ciuperci.in");
    ofstream outfile("ciuperci.out");

    int Q;
    infile >> Q;

    precompute();

    for (int i = 0; i < Q; ++i) {
        long long N;
        infile >> N;
        if (N <= MAXN) {
            outfile << dp[N] << endl;
        } else {
            outfile << 0 << endl;  // Since we cannot compute for N > MAXN
        }
    }

    infile.close();
    outfile.close();

    return 0;
}