t = [0, 0, 0, 1]
for i in range(1000000):
    t.append((t[i] + t[i+1] + t[i+2] + t[i+3]) % 17)

q = int(input())

for i in range(q):
    print(t[int(input())-1])