dp=[0 for i in range(1000001)]
dp[4]=1
for j in range(1000001-5):
	i=j+5
	dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]
	dp[i]%=17
q=int(input())
while q:
	q-=1
	n=int(input())
	print(dp[n])