Q = int(input())
T = [0 for _ in range(4912)]
T[3] = 1

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

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