Знаете ли вы, что такое оркестровые колокола? Это музыкальный инструмент, состоящий из цилиндрических металлических трубок. В оркестре колокола имитируют колокольный звон.

У Майка тоже есть оркестровые колокола! Они состоят из $$$n$$$ трубок, причем каждая из трубок имеет длину, которая может быть выражена целым числом от $$$l$$$ до $$$r$$$ включительно. Ясно, что длины всех трубок различны (нет смысла делать одинаковые трубки). Также известно, что $$$r-l+1 = n$$$.

Формально, можно сказать, что оркестровые колокола Майка описываются перестановкой $$$a$$$ длины $$$n$$$, которая содержит все числа от $$$l$$$ до $$$r$$$ включительно, причем $$$a_i$$$ обозначает длину $$$i$$$-й трубки.

Вам предлагается интересная задача: угадать, как выглядит инструмент Майка. Проще говоря, необходимо угадать перестановку.

Майк не скажет вам ни $$$l$$$, ни $$$r$$$. Он скажет вам только $$$n$$$, и разрешит задать не более, чем $$$n + 5000$$$ запросов.

В каждом запросе вы называете два целых положительных числа $$$x$$$, $$$y$$$ таких, что $$$1 \le x, y \le n, x \neq y$$$. В ответ на этот запрос программа, написанная Майком, выдаст вам $$$\mathrm{lcm}(a_x, a_y)$$$, где $$$\mathrm{lcm}(c,d)$$$ обозначает наименьшее общее кратное (НОК) чисел $$$c$$$ и $$$d$$$.

Решите задачу Майка!

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

Если вы хотите сделать запрос, выведите его в формате «? $$$x$$$ $$$y$$$», где $$$x$$$ и $$$y$$$ — номера трубок, для которых вы узнаете НОК их длин. Обратите внимание, что должно выполняться $$$1 \le x, y \le n, x \neq y$$$. Интерактор вернет вам в качестве ответа одно целое число — ответ на ваш запрос.

Если вы готовы вывести ответ, выводите его в формате «! $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$». Вывод ответа не считается запросом и не включается в количество допустимых запросов.

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

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

Обратите внимание, что интерактор не адаптивен. Это означает, что перестановка изначально фиксирована и не зависит от ваших запросов.

Взломы:

Для взломов используйте следующий формат:

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

В первой строке каждого набора входных данных находится одно целое положительное число $$$n$$$ ($$$3 \le n \le 10^5$$$) — количество трубок. Известно, что $$$1 \le l \le r \le 2 \cdot 10^5$$$, т.е. длины трубок не превосходят $$$2 \cdot 10^5$$$.

Во второй строке каждого набора входных данных находится массив $$$a$$$ из $$$n$$$ целых положительных чисел — длины трубок. Помните, что $$$l \le a_i \le r$$$ и $$$r-l+1 = n$$$, а также то, что все $$$a_i$$$ различны.