n = int(input())
index_list = [ int(input()) for i in range(n)] 

tetlist = [ 0 for i in range(1000000) ]
tetlist[4] = 1
for i in range(5,len(tetlist)):
	tetlist[i] = (tetlist[i-1] + tetlist[i-2] + tetlist[i-3] + tetlist[i-4]) % 17

for i in index_list:
	print(tetlist[i])