#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using mint = modint998244353;

int main() {
  vector<ll> T(1000001, 0);
  T[4] = 1;
  for (int i = 5; i <= 1000000; i++) {
    T[i] = (T[i - 4] + T[i - 3] + T[i - 2] + T[i - 1]) % 17;
  }
  int Q; cin >> Q;
  while (Q--) {
    int n; cin >> n;
    cout << T[n] << endl;
  }
  return 0;
}