#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
#define MAX 1000001
int main() {
  int T[MAX];
  T[1] = 0; T[2] = 0; T[3]=0; T[4]=1;
  for(int i=5; i<MAX; i++) {
    T[i] = (T[i-1]+T[i-2]+T[i-3]+T[i-4])%17;
  }
  int q;
  cin >> q;
  for(int i=0; i<q; i++) {
    int n;
    cin >> n;
    printf("%d\n", T[n]);
  }
  return 0;
}