T=[0,0,0,1]
for i in range(10**6):
    T.append(T[len(T)-1]+T[len(T)-2]+T[len(T)-3]+T[len(T)-4])

Q=int(input())
for i in range(Q):
    m=int(input())
    print(T[m-1]%17)