Это интерактивная задача.

У Кевина есть $$$n$$$ одноклассников, пронумерованных $$$1, 2, \ldots, n$$$. Каждая пара одноклассников может быть либо друзьями, либо нет.

Кевин хочет выбрать $$$2k$$$ одноклассников, чтобы сформировать $$$k$$$ команд, где в каждой команде будет ровно по $$$2$$$ человека. Каждый человек может принадлежать не более чем к одной команде.

Пусть $$$u_i$$$ и $$$v_i$$$ — два человека в $$$i$$$-й команде. Чтобы избежать потенциальных конфликтов, команды должны удовлетворять одному из двух условий:

• Для всех команд $$$i$$$ ($$$1\leq i \leq k$$$), одноклассники $$$u_i$$$ и $$$v_i$$$ являются друзьями.
• Для всех команд $$$i$$$ ($$$1\leq i \leq k$$$), одноклассники $$$u_i$$$ и $$$v_i$$$ не являются друзьями.

Кевин хочет определить максимальное число $$$k$$$, такое, что независимо от дружеских отношений между $$$n$$$ одноклассниками, он всегда сможет найти $$$2k$$$ человек для формирования команд. Далее ему нужно сформировать $$$k$$$ команд. Но спрашивать, дружат ли два одноклассника, неудобно, поэтому Кевин хочет добиться этого, спросив о статусе дружбы не более чем у $$$n$$$ пар одноклассников.

Интерактор является адаптивным. Это означает, что скрытые отношения между одноклассниками не фиксируются до взаимодействия и будут меняться во время взаимодействия.

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

Первая строка каждого набора входных данных содержит одно целое положительное число $$$n$$$ ($$$2\leq n \leq 10^5$$$) — количество одноклассников.

Сначала вы должны вывести целое число $$$k$$$ ($$$1\leq k\leq \frac{n}2$$$) — максимальное количество команд, которое вы можете сформировать.

Вы можете задавать вопросы. Для этого выведите строку вида $$$?\;u\;v$$$, где $$$1\leq u\neq v \leq n$$$. После этого прочитайте одно число $$$0$$$ или $$$1$$$ — являются ли они друзьями. $$$1$$$ означает, что они друзья, а $$$0$$$ означает, что нет.

Если вы хотите вывести ответ, выведите $$$!\;u_1\;v_1\;u_2\;v_2\;\ldots\;u_k\;v_k$$$. Вы должны вывести ровно $$$2k$$$ различных чисел. Затем взаимодействие продолжается со следующим набором входных данных.

Вы можете сделать не более $$$n$$$ запросов. Вывод ответа не учитывается при подсчете количества выполненных запросов.

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

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взломы

Интерактор для взломов не является адаптивным. Чтобы произвести взлом, используйте следующий формат.

Первая строка содержит слово «manual».

Вторая строка содержит единственное целое число $$$t$$$ ($$$1\leq t \leq 10^4$$$) — количество наборов входных данных.

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

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$\frac{n(n - 1)}{2}$$$, состоящую из '0' и '1', и указывающую на взаимосвязь между $$$(1, 2)$$$, $$$(1, 3)$$$, $$$\ldots$$$, $$$(1, n)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$\ldots$$$, $$$(2, n)$$$, $$$\ldots$$$, $$$(n - 1, n)$$$. '1' означает дружбу, а '0' означает её отсутствие.

Ниже приведён текст взлома, аналогичный примеру:

manual
2
3
011
5
1011101011

Сумма $$$n$$$ по всем наборам входных данных не должна превосходить $$$10^5$$$.

Существует дополнительное ограничение для взломов: сумма $$$\frac{n(n-1)}{2}$$$ по всем наборам входных данных не должна превосходить $$$10^7$$$.