#include <iostream>

#define NACCI 4

int main() {
    using namespace std;
    int q;
    cin >> q;
    int n[q];
    int p[1000000];
    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 = NACCI; i < 1000000; i++) {
        p[i] = 0;
        for (int j = 1; j < NACCI + 1; j++) {
            p[i] += p[i - j];
        }
        p[i] %= 17;
    }
    for (int i = 0; i < q; i++) {
        cout << p[n[i] - 1] << endl;;
    }
}