N=1000100
A=[0]*N
A[3]=1
for i in range(4,N):
    A[i]=A[i-1]+A[i-2]+A[i-3]+A[i-4]
    A[i]%=17

Q=int(input())
for _ in range(Q):
    p=int(input())
    p-=1
    print(A[p])