def tetra(qs):
    seed = [0, 0, 0, 1]
    res = dict([(x[0] + 1, x[1]) for x in enumerate(seed)])

    for step in range(5, max(qs) + 1):
        seed.append(sum(seed) % 17)
        seed = seed[1:]
        if step in qs:
            res[step] = seed[-1]

    return res


nq = int(input())
qs = [int(input()) for _ in range(nq)]

t = tetra(qs)

for q in qs:
    print(t[q])