dp=[0]*(10**6+1)
dp[4]=1
for i in range(5,10**6+1):
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]
    dp[i]%=17
q=int(input())
for _ in range(q):
    print(dp[int(input())])