mod = 17
T = [0 for _ in range(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]) % mod

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