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

#define ll long long

using namespace std;

int T[5000];

int main(){
  
  T[0]=T[1]=T[2]=0;
  T[3]=1;
  for(int i=4;i<=4912;++i) T[i]=(T[i-1]+T[i-2]+T[i-3]+T[i-4])%17;
  
  int q;
  cin>>q;
  ll p;
  for(int i=0;i<q;++i){
     cin>>p;
     cout<<T[(p-1)%4912]<<endl; //実験結果周期4912
  }
  return 0;
}