#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<int> T(1000000);
  T[0] = 0;
  T[1] = 0;
  T[2] = 0;
  T[3] = 1;
  for (int i = 4; i < 1000000; 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;
    cout << T[n - 1] << endl;
  }
}