#include <bits/stdc++.h>

using namespace std;

int dp[1000001];

int f(int idx) {
  if(idx <= 3) return (0);
  if(idx == 4) return (1);
  if(~dp[idx]) return (dp[idx]);
  return dp[idx] = (f(idx - 4) + f(idx - 3) + f(idx - 2) + f(idx - 1)) % 17;
}

int main() {

  memset(dp, -1, sizeof(dp));

  int Q;
  cin >> Q;
  while(Q--) {
    int X;
    cin >> X;
    cout << f(X) << endl;
  }
}