Это интерактивная задача. Не забывайте очищать буфер вывода после каждой печати. Для этого можно использовать:

• fflush(stdout) или cout.flush() в C/C++;
• System.out.flush() в Java и Kotlin;
• sys.stdout.flush() в Python;
• Для других языков обратитесь к документации.

У Little Cyan Fish есть секретная перестановка $p_0,p_1,\ldots,p_n$ длины $n+1$, состоящая из целых чисел от $0$ до $n$. Он хочет, чтобы вы угадали эту перестановку. Для этого Little Cyan Fish разрешает выполнить не более $1024$ запросов следующего вида:

• ? i j: Получить индекс $k$ ($0\le k\le n$), для которого $p_k=|p_i-p_j|$.

Разумеется, для корректного запроса нужно гарантировать, что $i$ и $j$ — целые числа из $[0,n]$. Например, если $p_0=2,p_1=0,p_2=1$, запрос ? 0 2 вернёт индекс $2$, поскольку $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish хочет, чтобы вы придумали стратегию нахождения перестановки. Конечно, он не хочет, чтобы вы выиграли слишком легко. Поэтому он будет адаптивно менять перестановку $p$, чтобы заманить вас в ловушку (подробнее см. «Протокол взаимодействия»).

Входные данные

Есть несколько наборов входных данных. Первая строка ввода содержит одно целое число $T$ ($1\le T\le100$), обозначающее количество наборов.

Для каждого набора первая строка ввода содержит одно целое число $n$ ($1\le n\le1000$). После этого начинается взаимодействие.

Протокол взаимодействия

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

$$?\ i\ j$$

Здесь $i$ и $j$ — два целых числа от $0$ до $n$. Необходимо гарантировать, что число запросов не превышает $1024$. В ответ вы получите целое число $k$, для которого $p_k=|p_i-p_j|$.

Чтобы сообщить ответ, выведите строку в следующем формате:

$$!\ p_0\ p_1\ \ldots\ p_n$$

Здесь $p$ — перестановка, которую вы хотите сообщить.

После вывода запроса или ответа не забудьте вывести перевод строки и очистить поток вывода.

В этой задаче интерактор адаптивный. Это означает, что перестановка $p$ может меняться в зависимости от ваших запросов, если это не противоречит предыдущим запросам.

Примеры

Пример взаимодействия 1

Чтение:

1
3

Запись:

? 2 2

Чтение:

1

Запись:

? 0 3

Чтение:

3

Запись:

! 2 0 3 1

Инструмент тестирования: Предоставлен инструмент, помогающий участникам разрабатывать и тестировать решения. Его можно скачать из вложений. Запуск с параметром -h должен вывести описание использования. Инструмент реализует лишь некоторые тестовые сценарии и часть возможностей настоящей проверяющей программы.