Вам задана система труб. Она состоит из двух рядов, каждый из которых состоит из $$$n$$$ труб. Верхняя левая труба имеет координаты $$$(1, 1)$$$, а нижняя правая — $$$(2, n)$$$.

Всего существует шесть типов труб: два типа прямых труб и четыре типа изогнутых труб. Ниже приведены примеры всех шести типов:

Типы труб

Вы можете поворачивать каждую из заданных труб на $$$90$$$ градусов по часовой или против часовой стрелки любое (возможно, нулевое) количество раз (таким образом, типы $$$1$$$ и $$$2$$$ могут переходить друг в друга, а также $$$3, 4, 5, 6$$$ могут переходить друг в друга).

Вы хотите повернуть некоторые трубы таким образом, чтобы поток воды мог начать свое движение в $$$(1, 0)$$$ (слева от верхней левой трубы), пойти по трубе в $$$(1, 1)$$$, как-то потечь по связным трубам до трубы $$$(2, n)$$$ и потечь вправо в $$$(2, n + 1)$$$.

Трубы называются связными, если они являются соседними в системе и их концы соединены. Ниже несколько примеров связных труб:

Примеры связных труб

Попробуем описать задачу при помощи примера:

Входные данные первого примера

И его решение ниже:

Решение первого примера

Как вы можете заметить, поток воды — это плохо нарисованная синяя линия. Чтобы достичь ответа, нам необходимо повернуть трубу на позиции $$$(1, 2)$$$ на $$$90$$$ градусов по часовой стрелке, трубу на позиции $$$(2, 3)$$$ на $$$90$$$ градусов, трубу на позиции $$$(1, 6)$$$ на $$$90$$$ градусов, трубу на позиции $$$(1, 7)$$$ на $$$180$$$ градусов и трубу на позиции $$$(2, 7)$$$ на $$$180$$$ градусов. Тогда поток воды сможет достичь $$$(2, n + 1)$$$ из $$$(1, 0)$$$.

Вам необходимо ответить на $$$q$$$ независимых запросов.