#include<iostream>
using namespace std;


int main(){
  int Q;
  int i,t;
  scanf("%d", &Q);
  int box[Q];
  int T[1000001] = {0,0,0,0,1};

  for(i = 5; i <= 1000000; i++){
    T[i] = T[i-1]+T[i-2]+T[i-3]+T[i-4];
  }

  for(i = 0; i < Q; i++){
    scanf("%d",&t);
    box[i] = t;
  }


  for(i = 0; i < Q; i++){
    printf("%d\n", T[box[i]]%17);
  }

}