Este es un problema interactivo. Recuerda vaciar el búfer de salida después de cada impresión. Para ello, puedes usar:

• fflush(stdout) o cout.flush() en C/C++;
• System.out.flush() en Java y Kotlin;
• sys.stdout.flush() en Python;
• Consulta la documentación de los demás lenguajes.

Little Cyan Fish tiene una permutación secreta $p_0,p_1,\ldots,p_n$ de longitud $n+1$, formada por los enteros de $0$ a $n$. Quiere que adivines la permutación secreta. Para ello, Little Cyan Fish te permite realizar como máximo $1024$ consultas de la siguiente forma:

• ? i j: Obtén el índice $k$ ($0\le k\le n$) tal que $p_k=|p_i-p_j|$.

Por supuesto, para que una consulta sea válida, debes garantizar que $i$ y $j$ sean dos enteros de $[0,n]$. Por ejemplo, si $p_0=2,p_1=0,p_2=1$, la consulta ? 0 2 devolverá el índice $2$, ya que $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish quiere que idees una estrategia para encontrar la permutación. Por supuesto, no quiere que ganes el juego demasiado fácilmente. Por ello, cambiará de forma adaptativa la permutación $p$ para tenderte una trampa (consulta «Interacción» para más detalles).

Entrada

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

Para cada caso de prueba, la primera línea de la entrada contiene un único entero $n$ ($1\le n\le1000$). Después comienza la interacción.

Interacción

Para realizar una consulta, imprime una línea con el siguiente formato:

$$?\ i\ j$$

Aquí $i$ y $j$ son dos enteros de $0$ a $n$. Debes garantizar que el número de consultas no supere $1024$. Como respuesta, recibirás un entero $k$ tal que $p_k=|p_i-p_j|$.

Para comunicar la respuesta, imprime una línea con el siguiente formato:

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

Aquí $p$ es la permutación que deseas comunicar.

Después de imprimir una consulta o comunicar la respuesta, no olvides imprimir un salto de línea y vaciar el flujo de salida.

En este problema, el interactor es adaptativo. Esto significa que la permutación $p$ puede cambiar según tus consultas, siempre que no contradiga las consultas anteriores.

Ejemplos

Ejemplo de interacción 1

Leer:

1
3

Escribir:

? 2 2

Leer:

1

Escribir:

? 0 3

Leer:

3

Escribir:

! 2 0 3 1

Herramienta de prueba: Se proporciona una herramienta para ayudar a los participantes a desarrollar y probar sus soluciones. Puedes descargarla de los archivos adjuntos. Al ejecutarla con la opción -h, debería describir cómo usarla. La herramienta solo implementa algunos escenarios de prueba y parte de las funciones del programa de evaluación real.