# 愚直にT[10**6]まで事前に求めておく

Q = int(input())
query = [int(input()) for _ in range(Q)]

T = [0] * (10**6 + 1)
T[4] = 1
for i in range(5,10**6+1):
    T[i] = (T[i-1] + T[i-2] + T[i-3] + T[i-4]) % 17


for n in query:
    print(T[n])