Это задача с двойным запуском (коммуникационная).

Левая Кружка и Правая Кружка ловят опасного преступника, прячущегося на улицах Железного города. Однако, поскольку они умеют только петь И отрицать происходящее, им также нужен кто-то, кто умеет хорошо делать XOR.

Представитель Административного Бюро (ПАБ) выполняет важное задание по тренировке своих агентов, ЛКП и ПКП. Для этого он проведет с ними серию из нескольких тестов. Каждый тест состоит из двух этапов. Во время проведения теста агенты не могут общаться друг с другом напрямую.

На первом этапе ЛКП получает целое число $$$n$$$ и бинарную строку $$$s$$$ длины $$$n - 1$$$. ЛКП должен вывести связный неориентированный граф на вершинах $$$1, 2, \ldots, n$$$ без петель и кратных рёбер.

После получения графа от ЛКП, ПАБ может применить к нему следующую операцию произвольное число раз (возможно, ни одного):

• выбрать целое число $$$k$$$ ($$$k \ge 2$$$) и простой$$$^{\text{∗}}$$$ путь $$$v_1, v_2, \ldots, v_{2k}$$$, состоящий из $$$2k$$$ вершин и $$$2k - 1$$$ рёбер;
• выбрать любой индекс $$$i$$$ ($$$1 \le i \le 2k-1$$$) и удалить из графа ребро между вершинами $$$v_i$$$ и $$$v_{i+1}$$$;
• если в графе нет ребра между вершинами $$$v_1$$$ и $$$v_{2k}$$$, добавить его.

Обратите внимание, что после операции количество рёбер может уменьшиться. Можно показать, что граф остаётся связным.

Перед передачей графа ПКП ПАБ может произвольным образом изменить порядок перечисления рёбер и поменять местами концы любого ребра. Это возможно, даже если ПАБ не выполнил ни одной операции.

На втором этапе ПАБ передаёт получившийся граф ПКП. ПКП должен восстановить исходную строку $$$s$$$. Найдите стратегию для обоих агентов, которая позволяет успешно пройти тест независимо от операций, выполненных ПАБ.

Ваша программа будет запущена дважды на каждом тесте: сначала как ЛКП, затем как ПКП. Это отдельные запуски; содержимое памяти программы между ними не сохраняется.

Первый запуск

Входные данные

Первая строка содержит строку first, обозначающую первый запуск.

После этой строки оставшиеся входные данные имеют следующий формат.

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^3$$$) — количество вершин.

Вторая строка содержит строку $$$s$$$ длины $$$n - 1$$$, состоящую только из символов 0 и 1.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^3$$$.

Выходные данные

Для каждого набора входных данных выведите целое число $$$m$$$ ($$$n - 1 \le m \le \frac{n(n - 1)}{2}$$$) — количество рёбер в вашем графе. В каждой из следующих $$$m$$$ строк выведите два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), описывающих ребро.

Граф должен быть связным и не содержать петель и кратных рёбер. Вы можете выводить рёбра и их концы в любом порядке.

Второй запуск

Входные данные

Первая строка содержит строку second, обозначающую второй запуск.

После этой строки оставшиеся входные данные имеют следующий формат.

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Значение $$$t$$$ совпадает со значением в первом запуске, однако наборы входных данных могут следовать в другом порядке.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 10^3$$$; $$$n - 1 \le m \le \frac{n(n - 1)}{2}$$$) — количество вершин и рёбер в получившемся графе. Значение $$$n$$$ совпадает со значением в соответствующем наборе входных данных первого запуска.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), описывающих неориентированное ребро.

Рёбра могут быть перечислены в любом порядке, а концы каждого ребра — в любом из двух порядков, даже если ПАБ не выполняет ни одной операции. Эти порядки могут отличаться от порядка в вашем выводе в первом запуске.

Гарантируется, что граф получен из вашего графа в первом запуске применением описанных выше операций произвольное число раз (возможно, ни одного). Можно показать, что получившийся граф связен и не содержит петель и кратных рёбер.

Выходные данные

Для каждого набора входных данных выведите исходную бинарную строку $$$s$$$ длины $$$n - 1$$$.