def t(n):
  t=[0]*3+[1]
  if n<5:return(t[n-1])
  for i in range(4,n):
    t+=[sum(t)%17]
    t.pop(0)
  return t.pop()
q=int(input())
n=[int(input()) for i in'.'*q]
for i in n:print(t(i))