lst = [0, 0, 0, 1] for i in range(4, 1000000): lst.append((lst[-1]+lst[-2]+lst[-3]+lst[-4])%17) Q = int(raw_input()) for i in range(0, Q): print lst[int(raw_input())-1]