def main():
    Q = int(input())
    N = tuple(int(input()) for _ in [0] * Q)

    lst = [i for i in tetra(max(N))]
    for n in N:
        print(lst[n-1])

def tetra(n):
    a, b, c, d = 0, 0, 0, 1
    for _ in range(n):
        yield a
        a, b, c, d = b, c, d, (a+b+c+d) % 17

main()