#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

int T[1000005];

int main(){
  T[4] = 1;
  REP(i,5,1000005){
    T[i] = T[i-1] + T[i-2] + T[i-3] + T[i-4];
    T[i] %= 17;
  }

  int Q;
  cin >> Q;
  rep(i,Q){
    int n;
    cin >> n;
    cout << T[n] << endl;
  }
  
  return 0;
}