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

У вас раньше была перестановка $$$\pi$$$ размера $$$n$$$. И теперь она пропала. Все, что у вас осталось, это старое устройство, которое вы сделали во время изучения теории групп. Чтобы попытаться восстановить $$$\pi$$$, вы можете ввести перестановку $$$f$$$ размера $$$n$$$ в это устройство. Затем устройство отобразит перестановку $$$\pi^{-1} \circ f \circ \pi$$$. Найдите $$$\pi$$$, используя не более двух взаимодействий с устройством.

Перестановка размера $$$n$$$ - это последовательность $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$. Композиция двух перестановок $$$a$$$ и $$$b$$$ - это перестановка $$$a \circ b$$$, такая что $$$(a \circ b)_i = b_{a_i}$$$. Иными словами, если мы рассматриваем перестановку как действие на $$$n$$$ элементах, перемещая элемент на позиции $$$i$$$ на позицию $$$a_i$$$, то $$$a \circ b$$$ - это действие, которое сначала применяет $$$a$$$, затем применяет $$$b$$$, так что элемент на позиции $$$i$$$ сначала перемещается на позицию $$$a_i$$$, затем перемещается на позицию $$$b_{a_i}$$$. Обратите внимание, что некоторые определения композиции используют обратный порядок.

Обратная перестановка $$$\pi^{-1}$$$ - это перестановка $$$\sigma$$$, такая что $$$\sigma_{\pi_i} = i$$$. Композиция перестановки и ее обратной равна единичной перестановке: $$$(\pi \circ \pi^{-1})_i = (\pi^{-1} \circ \pi)_i = i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$. Например, если $$$a = (4, 1, 3, 2)$$$ и $$$b = (3, 2, 1, 4)$$$, то $$$a \circ b = (4, 3, 1, 2)$$$, $$$a^{-1} = (2, 4, 3, 1)$$$ и $$$a^{-1} \circ b \circ a = (1, 2, 4, 3)$$$.

Ваша программа должна обрабатывать несколько тестовых случаев за один запуск. Сначала система тестирования записывает $$$t$$$, количество тестовых случаев ($$$t \ge 1$$$). Затем $$$t$$$ тестовых случаев должны быть обработаны один за другим.

В каждом тестовом случае ваша программа должна начать с чтения целого числа $$$n$$$ ($$$3 \le n \le 10^4$$$), размера перестановки $$$\pi$$$. Сумма $$$n$$$ по всем тестовым случаям не превышает $$$10^4$$$. Затем ваша программа может делать запросы двух типов:

• ? $$$f_1 \, f_2 \, \ldots \, f_n$$$, значения $$$f_1, f_2, \ldots, f_n$$$ образуют перестановку $$$1, 2, \ldots, n$$$. Система тестирования отвечает перестановкой $$$g_1, g_2, \ldots, g_n$$$, где $$$g = \pi^{-1} \circ f \circ \pi$$$.
• ! $$$\pi_1 \, \pi_2 \, \ldots \, \pi_n$$$ — ваше предположение о секретной перестановке.

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