Это интерактивная задача. В секции «Протокол взаимодействия» вы найдёте информацию о том, как сбрасывать буфер вывода (делать операцию 'flush').

Новогоднее дерево высоты h является полным двоичным деревом, вершины которого некоторым образом пронумерованы от 1 до 2^h - 1. В данной задаче мы будем считать, что h не меньше 2. Рисунок ниже изображает пример новогоднего дерева высоты 3:

Полярные медведи очень любят украшать новогодние деревья, и Лимак конечно же не исключение. Чтобы украсить дерево, ему требуется сначала найти его корень, то есть вершину у которой ровно два соседа (предполагая, что h ≥ 2). Маленькому медвежонку будет крайне непросто это сделать, так как он не может окинуть взглядом всё дерево. Сможете ли вы ему помочь?

Входных данные содержат t тестовых примеров. В начале каждого тестового примера на ввод подаётся единственное число h. Далее вы можете сделать не более 16 запросов в формате «? x», где x — некоторое целое число от 1 до 2^h - 1 включительно. В качестве ответа вам будет дан список всех соседей вершины x (подробнее смотрите секцию «Протокол взаимодействия»). Например если про дерево с картинки выше сделать запрос «? 1», то в качестве ответа будут получены 3 его соседа: 4, 5 и 7. Ваша задача — найти индекс корневой вершины y и сообщить его в формате запроса «! y». Вы сможете считать значение h для следующего тестового примера только после вывода ответа для предыдущего примера и выполнения операции 'flush'.

В каждом тестовом примере дерево фиксировано с самого начала и не изменяется в зависимости от запросов.

Чтобы запросить список соседей вершины x выведите «? x» (без кавычек) в отдельной строке. Не забудьте вывести символ конца строки и выполнить операцию 'flush' чтобы получить ответ.

Ответ на запрос состоит из двух строк. В первой из них записано целое число k (1 ≤ k ≤ 3) — количество соседей вершины x. Во второй строке записаны k различных целых чисел t₁, ..., t_k (1 ≤ t₁ < ... < t_k ≤ 2^h - 1) — индексы вершин смежных вершине x, перечисленные в порядке возрастания.

Сделав не более 16 запросов для одного тестового примера вы должны сообщить y — индекс корня дерева. Выведите «! y» (без кавычек) и символ конца строки, после чего выполните операцию 'flush'.

В каждом тестовом примере дерево фиксировано с самого начала и не изменяется в зависимости от запросов.

Если вы ничего не выведите или забудете сделать операцию 'flush', то можете получить вердикт Idleness Limit Exceeded.

Для сброса буфера вывода (то есть для операции 'flush') сразу после вывода числа или ответа и перевода строки можно сделать:

• fflush(stdout) в языке C++;
• System.out.flush() в Java;
• stdout.flush() в Python;
• flush(output) в Pascal;
• смотрите документацию для других языков.

Если в любой момент ваша программа считает h = 0 или k = 0 она должна немедленно завершиться с нулевым кодом возврата (например, вызовом exit(0)). Это означает, что проверяющая программа обнаружила некорректный запрос или вывод и вывела 0, так как не может дальше обрабатывать запросы. В этом случае вы получите вердикт «Wrong Answer», но если ваша программа не завершится после считывания h = 0 или k = 0 то это может привести к получению вердиктов «Runtime Error», «Time/Memory limit exceeded» или любых других поскольку ваша программа продолжит считывать мусор из уже закрытого потока ввода.

Взломы. Для взломов не разрешается использовать мультитест. Чтобы совершить взлом, используйте следующий формат входных данных:

В первой строке следует записать одно целое число t равное 1.

Во второй строке должно быть записано одно целое число h. В каждой из последующих 2^h - 2 строк должна быть записана пара целых чисел a_i и b_i (1 ≤ a_i, b_i ≤ 2^h - 1), означающая что две вершины с данными индексами соединены ребром. Выведенный набор рёбер должен задавать полное двоичное дерево высоты h.

Разумеется, это описание дерева не будет доступно взламываемому участнику.