Q = int(input())
queries = [int(input()) for _ in range(Q)]

def find_period_table():
    prev3, prev2, prev1, current = 0, 0, 0, 1
    state_map = {}
    state_map[(prev3, prev2, prev1, current)] = 4
    step = 4
    while True:
        next_val = (prev3 + prev2 + prev1 + current) % 17
        prev3, prev2, prev1, current = prev2, prev1, current, next_val
        step += 1
        state = (prev3, prev2, prev1, current)
        if state in state_map:
            period = step - state_map[state]
            break
        state_map[state] = step

    # Generate the table for one period
    prev3, prev2, prev1, current = 0, 0, 0, 1
    table = []
    for _ in range(period):
        next_val = (prev3 + prev2 + prev1 + current) % 17
        prev3, prev2, prev1, current = prev2, prev1, current, next_val
        table.append(current)
    return period, table

period, table = find_period_table()

for n in queries:
    if n <= 3:
        print(0)
    elif n == 4:
        print(1)
    else:
        idx = (n - 5) % period
        print(table[idx])