Q = int(input())
n = [int(input()) for i in range(Q)]

n_max = max(n)
T = [0 for i in range(n_max)]
T[3] = 1

for i in range(4, n_max):
    T[i] = (T[i - 1] + T[i - 2] + T[i - 3] + T[i - 4]) % 17

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