Gracias por tu arduo trabajo, cariño. Little Cyan Fish no sabe cuánto de sus palabras en clave se puede transmitir, pero aun así te agradece por haber caminado hasta este punto con Little Cyan Fish. Tantas cosas, tantas cosas absurdas sucedieron; Little Cyan Fish está cansado, muy cansado... En el último año, Little Cyan Fish sintió varias veces que iba a salvarse a sí mismo, pero al fin y al cabo, no era lo suficientemente fuerte como para cortar los hilos de su cuerpo. Little Cyan Fish siempre imagina que en ese lugar lejano hay otro yo que puede ver claramente el mapa de su vida.

— "Longing for the Distance" · Final del 10.º Concurso Universitario de Programación de China

Este es un problema interactivo.

Bueno, tal vez puedas intentarlo y ver qué tan difícil será. Little Cyan Fish siente que su vida es una permutación de forma desconocida. La gente siempre dice que el mundo está lleno de aleatoriedad, pero ¿por qué Little Cyan Fish siempre tiene tanta mala suerte...? ¡Ajá! ¡Quizás la aleatoriedad sea así de profunda! Así que Little Cyan Fish decide que esta permutación suya se generará aleatoriamente de la siguiente manera:

• Generar una permutación aleatoria $p_1, p_2, \dots, p_n$: elegida uniformemente al azar entre todas las $n!$ permutaciones posibles de $1$ a $n$.
• Si $p_1 > p_n$, entonces invertir toda la permutación.

No puedes observar directamente la estructura de la permutación, pero Little Cyan Fish te ha otorgado un superpoder: ¡preguntar! Cada vez, puedes consultar interactivamente el valor de la distancia entre dos números en la permutación módulo $3$. Específicamente, cada vez puedes elegir dos números $u, v$ ($1 \le u, v \le n$, $u \ne v$), y la permutación te dirá el valor de la distancia entre estos dos números módulo $3$ (es decir, encontrando dos índices $i, j$ que satisfagan $p_i = u, p_j = v$, la permutación responderá $|i - j| \bmod 3$).

Ahora, Little Cyan Fish quiere que lo intentes y veas qué puedes conseguir. Debes ayudar a Little Cyan Fish a determinar esta permutación en no más de $25n$ consultas.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T \le 1000$), que indica el número de casos de prueba.

Para cada caso de prueba, primero debes leer un entero $n$ ($3 \le n \le 10^4$).

Protocolo de interacción

A continuación, comienza la interacción. Puedes hacer no más de $25n$ consultas en cada caso de prueba. Para hacer una consulta, debes imprimir una sola línea ? u v ($1 \le u, v \le n$, $u \ne v$), describiendo una consulta. Luego, debes leer el resultado desde la entrada estándar.

Para proporcionar tu respuesta, debes imprimir ! p1 p2 ... pn. Tu salida debe satisfacer $p_1 < p_n$. Imprimir la respuesta no contará para el límite de $25n$ consultas. Después de imprimir la respuesta, debes leer el siguiente caso de prueba inmediatamente, o salir de tu programa inmediatamente.

Después de imprimir una consulta, no olvides imprimir un carácter de salto de línea y vaciar el flujo de salida (flush). Para ello, puedes usar fflush(stdout) o cout.flush() en C++, System.out.flush() en Java, flush(output) en Pascal y stdout.flush() en Python.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^4$.

En este problema, se garantiza que el interactor es no adaptativo. Es decir, las permutaciones se determinan aleatoriamente tal como se indica en el problema antes del proceso de interacción. No cambiarán según tus consultas. Hay un total de $30$ casos de prueba (incluyendo el caso de prueba de ejemplo).

Ejemplo

Entrada 1

2
3
2
1
1
4
1
1
1
0
2

Salida 1

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

Nota

Figura 1: Little Cyan Fish y <?> en <?> tomada el 4 de marzo de 2026