a = [0,0,0,0,1]
for _ in range(10**6):
    a.append(sum(a[-4:])%17)
Q = int(input())
for _ in range(Q):
    print(a[int(input())])