#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
using ll = long long;

int main(){
    int q;
    cin >> q;
    int k = 1e6;
    vector<int> v(k + 1);
    v[3] = 1;
    rep(i, 4, k + 1) {
        rep(j, 0, 4) {
            v[i] += v[i - 1 - j];
            v[i] %= 17;
        }
    }
    rep(i, 0, q) {
        int n;
        cin >> n;
        cout << v[n - 1] << endl;
    }
}