T=[0]*(10**6+1)
T[4]=1

for t in range(5,10**6+1):
    T[t]=(T[t-1]+T[t-2]+T[t-3]+T[t-4])%17

Q=int(input())
for _ in range(Q):
    n=int(input())
    print(T[n])