#include <bits/stdc++.h>
using namespace std;

long long t[1000001];

int main() {
  int q;
  cin>>q;
  t[1] = t[2] = t[3] = 0;
  t[4] = 1;
  for (int i=5; i<=1000000; i++) {
    t[i] = t[i-1] + t[i-2] + t[i-3] + t[i-4];
    t[i] %= 17;
  }
  for (int i=0; i<q; i++) {
    int n;
    cin>>n;
    cout<<t[n]<<endl;
  }

}