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]
    T[i] %= 17
Q = int(input())
for _ in range(Q):
    print(T[int(input())])