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

Q = int(input())
for _ in range(Q):
    n = int(input())
    print(T[n])