#include <iostream>

int main() {
    using namespace std;
    int q;
    cin >> q;
    long long n[q];
    int p[4912];
    p[0] = 0; p[1] = 0; p[2] = 0; p[3] = 1;
    for (int i = 0; i < q; i++) {
        cin >> n[i];
    }
    for (int i = 4; i < 4912; i++) {
        p[i] = 0;
        for (int j = 1; j < 4 + 1; j++) {
            p[i] += p[i - j];
        }
        p[i] %= 17;
    }
    for (int i = 0; i < q; i++) {
        cout << p[(n[i] - 1) % 4912] << endl;;
    }
}