query = [int(input()) for _ in [0]*int(input())]
a = [0, 0, 0, 0, 1]
append = a.append
for i in range(1, max(query)+1):
  append(sum(a[i:i+4])%17)
print("\n".join(map(lambda q: str(a[q]), query)))