T = [1] + [0] * 10 ** 6

for i in range(4, 10 ** 6 + 1):
    T[i] = (T[i - 1] + T[i - 2] + T[i - 3] + T[i - 4]) % 17
    
for _ in range(int(input())):
    print(T[int(input())])