n = int(input())
lst = [int(input()) for i in range(n)]
t = [0,0,0,0,1]
for i in range(1000000):
    t.append(sum(t[-4:])%17)
for i in lst:
    print(t[i])