lst = [0, 0, 0, 1]
for i in range(4, 1000000):
	lst.append((lst[-1]+lst[-2]+lst[-3]+lst[-4])%17)

Q = int(raw_input())
for i in range(0, Q):
	print lst[int(raw_input())-1]