Q = int(input())

T = [0, 0, 0, 1]

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

N = []
for _ in range(Q):
    N.append(int(input()))

for i in range(Q):
    print(T[N[i]-1])