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

Недавно состоялся турнир с $$$2^n$$$ участниками. Сначала $$$1$$$-й участник соревновался со $$$2$$$-м, $$$3$$$-й с $$$4$$$-м и так далее. После этого победитель первого матча соревновался с победителем второго и так далее. Турнир завершился, когда остался только один участник, этот участник стал победителем. Такая схема проведения турнира называется «олимпийской системой».

Вы не знаете результатов, но хотите определить победителя турнира. За один запрос вы можете выбрать два целых числа $$$a$$$ и $$$b$$$ — номера двух участников. Жюри ответит $$$1$$$, если $$$a$$$ выиграл больше матчей, чем $$$b$$$; $$$2$$$, если $$$b$$$ выиграл больше матчей, чем $$$a$$$; или $$$0$$$, если они выиграли поровну матчей.

Найдите победителя турнира за не более чем $$$\left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil$$$ запросов. Здесь $$$\lceil x \rceil$$$ обозначает значение $$$x$$$, округленное вверх до ближайшего целого числа.

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

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

Чтобы сделать запрос, выведите «? a b» ($$$1 \leq a, b \leq 2^n$$$) без кавычек. После этого считайте одно целое число — ответ на запрос. Вы можете сделать не более $$$\left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil$$$ таких запросов в каждом наборе входных данных.

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

Когда вы готовы дать ответ, выведите «! x» ($$$1 \leq x \leq 2^n$$$) без кавычек — номер победителя турнира. Вывод этого ответа не учитывается в ограничении на количество запросов. После этого ваша программа должна сразу перейти к решению следующего набора входных данных. После решения всех наборов входных данных ваша программа должна завершиться.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

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

Hacks

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2^{14}$$$) — количество наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$2^n$$$ целых чисел на одной строке — количество выигранных матчей для каждого участника. Количество выигранных матчей должно соответствовать некоторому корректному турниру.

Сумма значений $$$2^n$$$ не должна превышать $$$2^{17}$$$.