n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))

tet = [0,0,0,1]
ans = [0,0,0,1]
for i in range(999999):
    sm = sum(tet)
    ans.append(sm%17)
    tet.append(sm%17)
    tet = tet[-4:]
    
for i in ls:
    print(ans[i-1])