#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>

#define ll long long

using namespace std;

int T[1000001];

int main(){
  
  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])%17;
  
  int q;
  cin>>q;
  int p;
  for(int i=0;i<q;++i){
     cin>>p;
     cout<<T[p]<<endl;
  }

  return 0;
}