Q=int(input())

T=[0,0,0,0,1]
for i in range(5,1000000):
    T.append((T[i-1]+T[i-2]+T[i-3]+T[i-4])%17)

for i in range(Q):
    print(T[int(input())])