Дякую за твою нелегку працю, любий друже. 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 року