Q=int(input())
N=[]
for _ in range (Q):
    N.append(int(input()))


T=[0,0,0,0,1]

i=1
while i<max(N):
    if i<=4:    
        T.append((T[i]+T[i+1]+T[i+2]+T[i+3])%17)
    else:
        T.append((2*T[i+3]-T[i-1])%17)
    i+=1
    

for n in N: 
    print(T[n])