MOD = 17
T = [0, 0, 0, 1]

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

Q = int(input())
for i in range(Q):
    n = int(input()) - 1
    print(T[n])