N=1000000
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])%17
for _ in range(int(input())):
    print(a[int(input())-1])