//Normal

#define _GLIBCXX_DEBUG
#define ll long long
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void print(auto a){
  cout << a;
}

void prints(auto a){
  cout << a << " ";
}

void prints(){
  cout << " ";
}

void printl(auto a){
  cout << a << endl;
}

void printl(){
  cout << endl;
}

void fix(int n){
  cout << fixed << setprecision(n);
}

int main(){
  vector<int> X(2e6, 0);
  X[4] = 1;

  for(int i = 5; i <= 1e6; i++){
    X[i] = X[i-4]+X[i-3]+X[i-2]+X[i-1];

    X[i] %= 17;
  }

  int Q; cin >> Q;
  for(int i = 0; i < Q; i++){
    int M; cin >> M;

    printl(X[M]);
  }

  return 0;
}