Рассмотрим игру. В ряд лежат n шариков двух цветов: черные и белые. Позиции в ряду пронумерованы от 1 до n. Вам известно только общее количество шариков (n); точное их расположение и даже количество белых шариков неизвестно.

Вы можете делать запросы вида v u, где 1 ≤ v, u ≤ n. Если на позиции v находится чёрный шарик, а на позиции u — белый, то эти шарики поменяют местами (иначе не произойдёт ничего). При этом вам не сообщают, поменяли шарики местами или нет.

После некоторого (возможно, нулевого) числа таких запросов вы должны сделать «утверждение». «Утверждение» — это тоже две позиции v, u. Вам нужно угадать две такие позиции в ряду, что там лежат шарики одного и того же цвета.

Ваша задача — выдать последовательность запросов, за которой следует ровно одно «утверждение».

В одном тесте может быть много игр. Более того, во всех тестах, кроме первого, ровно 99 игр, причём в первой игре n = 2, во второй игре n = 3 и т. д.. В последней игре n = 100.

Первый тест совпадает с примером из условия. На нём проверяется только формат вывода.

На всех тестах, начиная со второго, чтобы пройти тест, ваша программа должна угадать хотя бы в 80 играх из 99.

Обратите внимание, что, хоть ваша программа и не должна выигрывать все 99 игр, мы не гарантируем, что тесты случайные.

В первой строке ввода записано одно число m — количество игр в этом тесте. Для всех тестов, кроме первого, m=99.

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

Выведите ровно m описаний игр.

Одно описание игры состоит из k + 1 строк, где k — количество сделанных вашей программой запросов.

В первых k строках выводятся эти запросы (в порядке применения) в формате ? v u (1 ≤ v, u ≤ n, v ≠ u).

В последней строке описания выводится ! v u (1 ≤ v, u ≤ n, v ≠ u) — ваше «утверждение».

Общее количество выведенных строк (суммарно по всем играм внутри одного теста) не должно превышать 5 · 10⁵.

В примере из условия белые шарики обозначены как 0, чёрные — как 1. Рассмотрим его подробнее.

Первая игра: 01 → 01 → 10 → 01 — мы не угадали.

Вторая игра: 101 → 011 → 110 — мы угадали.

Так, на этом тесте мы угадали в одной игре из двух.