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


T=[0,0,0,0,1]
for _ in range (max(N)-4):
    T+=[sum(T[-4:])%17]
            
for n in N: 
    print(T[n]%17)