#include <cstdio>
const int mod = 9901;
int m[6][6] = { 1, 2, 6, 1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0}, a[6][6], b[6][6], r[6][6];
int v[6] = { 170, 62, 23, 10, 3, 1 };
int main() {
int T, n;
for (scanf("%d", &T); T--;) {
scanf("%d", &n);
if (n == 0) printf("0\n");
if (n == 1) printf("1\n");
if (n == 2) printf("3\n");
if (n == 3) printf("10\n");
if (n == 4) printf("23\n");
if (n == 5) printf("62\n");
if (n == 6) printf("170\n");
if (n >= 7) {
bool first = true;
n -= 6;
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) a[i][j] = r[i][j] = m[i][j];
while (n) {
if (n & 1) {
if (first) {
first = false;
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) r[i][j] = a[i][j];
}
else {
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) b[i][j] = 0;
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) for (int k = 0; k < 6; k++) b[i][j] = (b[i][j] + a[i][k] * r[k][j]) % mod;
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) r[i][j] = b[i][j];
}
}
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) b[i][j] = 0;
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) for (int k = 0; k < 6; k++) b[i][j] = (b[i][j] + a[i][k] * a[k][j]) % mod;
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) a[i][j] = b[i][j];
n /= 2;
}
int res = 0;
for (int i = 0; i < 6; i++) res = (res + r[0][i] * v[i]) % mod;
printf("%d\n", (res + mod) % mod);
}
}
}
I2luY2x1ZGUgPGNzdGRpbz4KY29uc3QgaW50IG1vZCA9IDk5MDE7CmludCBtWzZdWzZdID0geyAxLCAyLCA2LCAxLCAwLCAtMSwgMSwgMCwgMCwgMCwgMCwgMCwgMCwgMSwgMCwgMCwgMCwgMCwgMCwgMCwgMSwgMCwgMCwgMCwgMCwgMCwgMCwgMSwgMCwgMCwgMCwgMCwgMCwgMCwgMSwgMH0sIGFbNl1bNl0sIGJbNl1bNl0sIHJbNl1bNl07CmludCB2WzZdID0geyAxNzAsIDYyLCAyMywgMTAsIDMsIDEgfTsKaW50IG1haW4oKSB7CglpbnQgVCwgbjsKCWZvciAoc2NhbmYoIiVkIiwgJlQpOyBULS07KSB7CgkJc2NhbmYoIiVkIiwgJm4pOwoJCWlmIChuID09IDApIHByaW50ZigiMFxuIik7CgkJaWYgKG4gPT0gMSkgcHJpbnRmKCIxXG4iKTsKCQlpZiAobiA9PSAyKSBwcmludGYoIjNcbiIpOwoJCWlmIChuID09IDMpIHByaW50ZigiMTBcbiIpOwoJCWlmIChuID09IDQpIHByaW50ZigiMjNcbiIpOwoJCWlmIChuID09IDUpIHByaW50ZigiNjJcbiIpOwoJCWlmIChuID09IDYpIHByaW50ZigiMTcwXG4iKTsKCQlpZiAobiA+PSA3KSB7CgkJCWJvb2wgZmlyc3QgPSB0cnVlOwoJCQluIC09IDY7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgNjsgaSsrKSBmb3IgKGludCBqID0gMDsgaiA8IDY7IGorKykgYVtpXVtqXSA9IHJbaV1bal0gPSBtW2ldW2pdOwoJCQl3aGlsZSAobikgewoJCQkJaWYgKG4gJiAxKSB7CgkJCQkJaWYgKGZpcnN0KSB7CgkJCQkJCWZpcnN0ID0gZmFsc2U7CgkJCQkJCWZvciAoaW50IGkgPSAwOyBpIDwgNjsgaSsrKSBmb3IgKGludCBqID0gMDsgaiA8IDY7IGorKykgcltpXVtqXSA9IGFbaV1bal07CgkJCQkJfQoJCQkJCWVsc2UgewoJCQkJCQlmb3IgKGludCBpID0gMDsgaSA8IDY7IGkrKykgZm9yIChpbnQgaiA9IDA7IGogPCA2OyBqKyspIGJbaV1bal0gPSAwOwoJCQkJCQlmb3IgKGludCBpID0gMDsgaSA8IDY7IGkrKykgZm9yIChpbnQgaiA9IDA7IGogPCA2OyBqKyspIGZvciAoaW50IGsgPSAwOyBrIDwgNjsgaysrKSBiW2ldW2pdID0gKGJbaV1bal0gKyBhW2ldW2tdICogcltrXVtqXSkgJSBtb2Q7CgkJCQkJCWZvciAoaW50IGkgPSAwOyBpIDwgNjsgaSsrKSBmb3IgKGludCBqID0gMDsgaiA8IDY7IGorKykgcltpXVtqXSA9IGJbaV1bal07CgkJCQkJfQoJCQkJfQoJCQkJZm9yIChpbnQgaSA9IDA7IGkgPCA2OyBpKyspIGZvciAoaW50IGogPSAwOyBqIDwgNjsgaisrKSBiW2ldW2pdID0gMDsKCQkJCWZvciAoaW50IGkgPSAwOyBpIDwgNjsgaSsrKSBmb3IgKGludCBqID0gMDsgaiA8IDY7IGorKykgZm9yIChpbnQgayA9IDA7IGsgPCA2OyBrKyspIGJbaV1bal0gPSAoYltpXVtqXSArIGFbaV1ba10gKiBhW2tdW2pdKSAlIG1vZDsKCQkJCWZvciAoaW50IGkgPSAwOyBpIDwgNjsgaSsrKSBmb3IgKGludCBqID0gMDsgaiA8IDY7IGorKykgYVtpXVtqXSA9IGJbaV1bal07CgkJCQluIC89IDI7CgkJCX0KCQkJaW50IHJlcyA9IDA7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgNjsgaSsrKSByZXMgPSAocmVzICsgclswXVtpXSAqIHZbaV0pICUgbW9kOwoJCQlwcmludGYoIiVkXG4iLCAocmVzICsgbW9kKSAlIG1vZCk7CgkJfQoJfQp9