N = int(input())
t=[int(input()) for i in range(N)]
for j in range(len(t)):
    if 1<=t[j]<=3:
        print(0)
    elif t[j]==4:
        print(1)
    else:
        s=[0,0,0,1]
        for i in range(t[j]-4):
            tt=2
            tt=s[0+i]+s[1+i]+s[2+i]+s[3+i]
            s.append(tt%17)
        print(tt%17)