#include <stdio.h>

struct Matrix {
    int a_11, a_12, a_21, a_22;
};

Matrix matrix_multiply(Matrix &mat1, Matrix &mat2) {
    return Matrix{(mat1.a_11 * mat2.a_11 + mat1.a_12 * mat2.a_21) % 9973,
                  (mat1.a_11 * mat2.a_12 + mat1.a_12 * mat2.a_22) % 9973,
                  (mat1.a_21 * mat2.a_11 + mat1.a_22 * mat2.a_21) % 9973,
                  (mat1.a_21 * mat2.a_12 + mat1.a_22 * mat2.a_22) % 9973};
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int ai;
        scanf("%d", &ai);
        if (ai <= 2) {
            printf("1\n");
            continue;
        }
        ai -= 2;
        Matrix multiply = Matrix{1, 1, 1, 0};
        Matrix result = Matrix{1, 0, 0, 1};
        Matrix orig = Matrix{1, 0, 1, 0};
        while (ai > 0) {
            if (ai & 1) {
                result = matrix_multiply(result, multiply);
            }
            multiply = matrix_multiply(multiply, multiply);
            ai = ai >> 1;
        }
        result = matrix_multiply(result, orig);
        printf("%d\n", result.a_11);
    }
    return 0;
}