import sys
input=lambda: sys.stdin.readline().rstrip()
q=int(input())
T=[0]*(10**6+1)
T[4]=1
for i in range(5,10**6+1):
  T[i]=(T[i-1]+T[i-2]+T[i-3]+T[i-4])%17
for _ in range(q):
  print(T[int(input())])