MOD = 17
Q = int(input())
T = [0]*(10**6+1)
T[4] = 1
for i in range(5,10**6+1):
    T[i] = (T[i-1]+T[i-2]+T[i-3]+T[i-4])%MOD
for _ in range(Q):
    print(T[int(input())])