Q = int(input())
N = [int(input()) for _ in range(Q)]
seq = [0] * 1001000
seq[4] = 1
for i in range(5,1000500):
    seq[i] = (seq[i-1] + seq[i-2] + seq[i-3] + seq[i-4])%17
for n in N:
    print(seq[n])