#include <iostream>
using namespace std;

int N;
struct matrix {
    int r, c;
    int** mat;

    matrix(int r, int c, int v[]) : r(r), c(c) {
        mat = new int*[r];
        for (int i=0; i < r; ++i) {
            mat[i] = new int[c];
        }
        for (int i=0; i < r; ++i) {
            for (int j=0; j < c; ++j) {
                mat[i][j] = v[i*c+j];
            }
        }
    }
    matrix(matrix& other){
        r=other.c; c = other.c;
        mat = new int*[r];
        for (int i=0; i < r; ++i) {
            mat[i] = new int[c];
        }
        copy(other);
    }
    ~matrix() {
        for (int i=0; i < r; ++i) {
            if (c > 1) {
                delete[] mat[i];
            } else {
                delete mat[i];
            }
        }
        if (r > 1) {
            delete[] mat;
        } else {
            delete mat;
        }
    }
    void identify() {
        for (int i=0; i < r; ++i) {
            for(int j=0; j < c; ++j) {
                mat[i][j] = (i==j);
            }
        }
    }
    void copy(matrix& other) {
        this->r = other.r;
        this->c = other.c;
        for (int i=0; i < r; ++i) {
            for (int j=0; j < c; ++j) {
                mat[i][j] = other.mat[i][j];
            }
        }
    }
    void multiply(matrix& out, matrix& other) {
        for (int i=0; i < this->r; ++i) {
            for (int j=0; j < other.c; ++j) {
                int& v = out.mat[i][j] = 0;
                for (int k=0; k < this->c; ++k) {
                     v = (v+this->mat[i][k]*other.mat[k][j]) % 9901;
                }
            }
        }
    }

    void pow(int n) {
        matrix out(*this);
        pow(out, n);
        copy(out);
    }

    void pow(matrix& out, int n) {
        if (n == 0) {
            out.identify();
        } else if ((n%2) == 1) {
            pow(out, n-1);
            matrix a(out);
            multiply(out, a);
        } else {
            pow(out, n/2);
            matrix a(out), b(out);
            a.multiply(out, b);
        }
    }
};


int tiling() {
    int T[] = {10, 3, 1};
    matrix out(3,1,T);
    if (N < 4) {
        return out.mat[3-N][0];
    }
    int C[] = {
        1, 2, 5,
        1, 0, 0,
        0, 1, 0
    };
    matrix w(3,3,C);
    matrix m(3,1,T);
    w.pow(N-3);
    w.multiply(out, m);
    return out.mat[0][0];
}

int main(const int argc, const char** argv) {
    int T; cin >> T;
    while (T--) {
        cin >> N;
        cout << tiling() << endl;
    }
    return 0;
}