Спасибо за твой нелёгкий труд, дорогой друг. Little Cyan Fish не знает, сколько его зашифрованных слов удастся передать, но всё равно благодарит тебя за то, что ты дошёл до этой точки вместе с Little Cyan Fish. Произошло так много всего, так много нелепых вещей, Little Cyan Fish устал, очень устал... За прошедший год Little Cyan Fish несколько раз чувствовал, что вот-вот спасёт себя сам, но, в конце концов, он оказался недостаточно силён, чтобы перерезать нити на своём теле. Little Cyan Fish всегда представляет, что в том далёком месте есть другой он сам, который может ясно видеть карту его жизни.

— «Стремление вдаль» · Финал 10-го Китайского студенческого чемпионата по программированию

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

Что ж, возможно, вы можете попробовать и узнать, насколько это будет сложно. Little Cyan Fish чувствует, что его жизнь — это перестановка неизвестной формы. Люди всегда говорят, что мир полон случайностей, но почему Little Cyan Fish всегда так не везёт?.. Ага! Быть может, случайность просто настолько глубока! Поэтому Little Cyan Fish решает, что эта его перестановка будет случайно сгенерирована следующим образом:

• Сгенерировать случайную перестановку $p_1, p_2, \dots, p_n$: она выбирается равновероятно из всех $n!$ возможных перестановок чисел от $1$ до $n$.
• Если $p_1 > p_n$, то развернуть всю перестановку задом наперёд.

Вы не можете напрямую наблюдать структуру перестановки, но Little Cyan Fish даровал вам суперспособность: задавать вопросы! Каждый раз вы можете интерактивно запросить значение расстояния между двумя числами в перестановке по модулю $3$. А именно, каждый раз вы можете выбрать два числа $u, v$ ($1 \le u, v \le n$, $u \ne v$), и перестановка сообщит вам значение расстояния между этими двумя числами по модулю $3$ (то есть, найдя два индекса $i, j$, удовлетворяющих $p_i = u, p_j = v$, перестановка ответит $|i - j| \bmod 3$).

Теперь Little Cyan Fish хочет, чтобы вы попробовали и посмотрели, что у вас получится. Вам нужно помочь Little Cyan Fish определить эту перестановку не более чем за $25n$ запросов.

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

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

В каждом наборе входных данных сначала вам нужно считать одно целое число $n$ ($3 \le n \le 10^4$).

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

Далее начинается взаимодействие. В каждом наборе входных данных вы можете сделать не более $25n$ запросов. Чтобы сделать запрос, вам нужно вывести одну строку ? u v ($1 \le u, v \le n$, $u \ne v$), описывающую запрос. Затем вам нужно считать результат из стандартного потока ввода.

Чтобы дать ответ, вам нужно вывести ! p1 p2 ... pn. Ваш вывод должен удовлетворять условию $p_1 < p_n$. Вывод ответа не учитывается в ограничении в $25n$ запросов. После вывода ответа вам нужно немедленно перейти к чтению следующего набора входных данных или немедленно завершить программу.

После вывода запроса не забудьте вывести символ перевода строки и сбросить буфер вывода (flush). Для этого вы можете использовать fflush(stdout) или cout.flush() в C++, System.out.flush() в Java, flush(output) в Pascal и stdout.flush() в Python.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $10^4$.

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

Пример

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

2
3
2
1
1
4
1
1
1
0
2

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

? 1 2
? 2 3
? 1 3
! 1 3 2
? 2 3
? 3 1
? 1 4
? 2 4
? 2 1
! 2 3 1 4

Примечание

Рисунок 1: Little Cyan Fish и <?> в <?>, снято 4 марта 2026 года