q=int(input())
n=[int(input())for i in range(q)]
a=10**6
t=[0]*a
t[3]=1
for i in range(4,a):
    t[i]=(t[i-4]+t[i-3]+t[i-2]+t[i-1])%17
for j in n:
    print(t[j-1])