#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  vector<Int> t({0,0,0,1});
  for(Int i=0;i<1.1e6;i++)
    t.emplace_back((t[i]+t[i+1]+t[i+2]+t[i+3])%17);
  Int q;
  cin>>q;
  for(Int i=0;i<q;i++){
    Int n;
    cin>>n;
    cout<<t[n-1]<<endl;
  }
  return 0;
}