#include<stdio.h>
#include<iostream>
using namespace std;
int main (){
    int t[1010101];
    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        int n;
        cin >> n;
        for(int j=0; j<n; j++){
            if( j < 3 ) t[j] = 0;
            else if ( j == 3 ) t[j] = 1;
            else t[j] = t[j-1] + t[j-2] + t[j-3] + t[j-4];
        }
        cout << t[n-1] % 17 << endl;
    }
    return 0;
}