#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
    vector<ll> dp(1000000);
    dp[0] = 0,dp[1] = 0,dp[2] = 0,dp[3] = 1;
    for(int i = 4;i < 1000000;i++){
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4];
        dp[i] %= 17;
    }
    ll q;
    cin >> q;
    for(int i = 0;i < q;i++){
        ll in;
        cin >> in;
        cout << dp[in - 1] << endl;
    }
}