N = int(input()) t=[int(input()) for i in range(N)] s=[0,0,0,1] for i in range(10**6): tt=s[0+i]+s[1+i]+s[2+i]+s[3+i] s.append(tt%17) for j in range(N): print(s[t[j]-1])