Q = int(input())
L = [int(input()) for _ in range(Q)]

N = 10**6 + 1
T = [0]*N
T[4] = 1
for i in range(5, N):
    T[i] = T[i-1] + T[i-2] + T[i-3] + T[i-4]
    T[i] %= 17

for q in L:
    print(T[q])