Hay $N$ ciclistas $1, \dots, N$. Cada ciclista tiene una habilidad distinta del $1$ al $N$, y cuando dos ciclistas se enfrentan, el ciclista con mayor habilidad siempre gana.

A los ciclistas les gusta participar en competiciones. En una competición, los ciclistas se ordenan en una lista cíclica. La competición se desarrolla entonces en rondas. En cada ronda, un ciclista compite contra cada uno de sus vecinos. Si pierde contra ambos, es eliminado.

Usted no conoce las habilidades de los ciclistas y desea descubrirlas. Puede organizar competiciones con todos los ciclistas, eligiendo cómo se ordenan en la lista cíclica cada vez, y se le informará en qué ronda fue eliminado cada ciclista.

Determine las habilidades utilizando el número óptimo de competiciones, o utilizando $N$ competiciones para obtener una puntuación parcial.

Interacción

Cada prueba contiene múltiples casos de prueba. La interacción comienza con una línea que contiene el número entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba.

Cada caso de prueba comienza con una línea que contiene el número entero $N$ ($3 \le N \le 300$), el número de ciclistas.

A continuación, puede realizar competiciones. Para realizar una competición, imprima una línea “? $a_1$ $a_2$ $\dots$ $a_n$” — $a_k$ indica que el ciclista $a_k$ está en la posición $k$-ésima de la lista de ciclistas. La lista $a_1, \dots, a_n$ debe ser una permutación de $1, \dots, n$.

La respuesta a su consulta será una línea “$r_1$ $r_2$ $\dots$ $r_n$” — $r_k$ satisface $0 \le r_k < n$. Cuando $r_k > 0$, indica que el ciclista en la posición $k$-ésima fue eliminado en la ronda $r_k$ de la competición. Si $r_k = 0$, entonces dicho ciclista ganó la competición.

Una vez que haya determinado las habilidades de los ciclistas, imprima una línea “! $s_1$ $s_2$ $\dots$ $s_n$” — $s_k$ debe ser igual a la habilidad del ciclista $k$.

Si realiza una consulta no válida o intenta realizar más de $N$ competiciones, su solución recibirá un veredicto de Respuesta Incorrecta (Wrong Answer). Además, si el conjunto de habilidades que imprime es diferente del conjunto de habilidades que el interlocutor tiene en mente, su solución recibirá un veredicto de Respuesta Incorrecta. En ambos casos, la interacción terminará inmediatamente. De lo contrario, recibirá una puntuación como se describe en la sección de puntuación.

Tenga en cuenta que el interlocutor puede ser adaptativo: las verdaderas habilidades de los ciclistas pueden cambiar a lo largo de la interacción, pero el conjunto actual de habilidades siempre será consistente con todas las competiciones anteriores.

Puntuación

Para cada caso de prueba, sea $q$ el número de competiciones que su solución realizó. Además, para cada $N$, sea $c_N$ el número mínimo de competiciones necesarias para garantizar la capacidad de determinar las habilidades.

Recibirá 100 puntos si $q \le c_N$ para todos los casos de prueba. De lo contrario, recibirá 10 puntos. Tenga en cuenta que, bajo las restricciones del problema, recibir 10 puntos requiere que usted satisfaga $q \le N$ para todos los casos de prueba.

Ejemplos

Entrada 1

1
5 Fixed
4 2 1 5 3

Salida 1

>>> 1
>>> 5
? 1 2 3 4 5
3 2 1 0 1
? 1 3 5 2 4
3 1 2 1 0
? 1 4 2 5 3
3 0 1 2 1
! 4 2 1 5 3

Nota

En el ejemplo, las habilidades de los ciclistas son 4, 2, 1, 5, 3 respectivamente.

En la primera competición realizada, los ciclistas se ordenan en la lista [1, 2, 3, 4, 5]. La competición procede de la siguiente manera; en cada ronda se muestra la lista de ciclistas con los eliminados reemplazados por X.

• En la ronda 1:
  • El ciclista en la posición 3 (ciclista 3 con habilidad 1) pierde contra los ciclistas en las posiciones 2 y 4 (ciclistas 2, 4 con habilidades 2, 5) y es eliminado.
  • El ciclista en la posición 5 (ciclista 5 con habilidad 3) pierde contra los ciclistas en las posiciones 4 y 1 (ciclistas 4, 1 con habilidades 5, 4) y es eliminado.
  • El ciclista en la posición 1 (ciclista 1 con habilidad 4) vence a los ciclistas en las posiciones 5, 2 (ciclistas 5, 2 con habilidades 3, 2) y por lo tanto no es eliminado.
  • El ciclista en la posición 2 (ciclista 2 con habilidad 2) vence al ciclista en la posición 3 (ciclista 3 con habilidad 1) y por lo tanto no es eliminado.
  • El ciclista en la posición 4 (ciclista 4 con habilidad 5) vence a los ciclistas en las posiciones 3, 5 (ciclistas 3, 5 con habilidades 1, 3) y por lo tanto no es eliminado.
• En la ronda 2, la lista de ciclistas es [1, 2, X, 4, X].
  • El ciclista en la posición 2 pierde contra los ciclistas en las posiciones 1 y 4 y es eliminado.
  • El ciclista en la posición 1 vence al ciclista en la posición 2 y por lo tanto no es eliminado.
  • El ciclista en la posición 4 vence a los otros dos ciclistas y por lo tanto no es eliminado.
• En la ronda 3, la lista de ciclistas es [1, X, X, 4, X].
  • El ciclista en la posición 1 pierde contra los ciclistas en las posiciones 4 y 4 (que son el mismo ciclista) y es eliminado.
  • El ciclista en la posición 4 vence al ciclista en la posición 1 y por lo tanto no es eliminado.

Por lo tanto: El ciclista en la posición 1 fue eliminado en la ronda 3. El ciclista en la posición 2 fue eliminado en la ronda 2. El ciclista en la posición 3 fue eliminado en la ronda 1. El ciclista en la posición 4 ganó la competición. * El ciclista en la posición 5 fue eliminado en la ronda 1.

haciendo que la respuesta a la consulta sea [3, 2, 1, 0, 1].

En la segunda competición realizada, los ciclistas se ordenan en la lista [1, 3, 5, 2, 4]. La competición procede de la siguiente manera:

• En la ronda 1:
  • El ciclista en la posición 2 (ciclista 3 con habilidad 1) pierde contra los ciclistas en las posiciones 1 y 3 (ciclistas 1, 5 con habilidades 4, 3) y es eliminado.
  • El ciclista en la posición 4 (ciclista 2 con habilidad 2) pierde contra los ciclistas en las posiciones 3 y 5 (ciclistas 5, 4 con habilidades 3, 5) y es eliminado.
  • El ciclista en la posición 1 (ciclista 1 con habilidad 4) vence al ciclista en la posición 2 (ciclista 3 con habilidad 1) y por lo tanto no es eliminado.
  • El ciclista en la posición 3 (ciclista 5 con habilidad 3) vence a los ciclistas en las posiciones 2, 4 (ciclistas 3, 2 con habilidades 1, 2) y por lo tanto no es eliminado.
  • El ciclista en la posición 5 (ciclista 4 con habilidad 5) vence a los ciclistas en las posiciones 4, 1 (ciclistas 2, 1 con habilidades 2, 4) y por lo tanto no es eliminado.
• En la ronda 2, la lista de ciclistas es [1, X, 5, X, 4].
  • El ciclista en la posición 3 pierde contra los ciclistas en las posiciones 1 y 5 y es eliminado.
  • El ciclista en la posición 1 vence al ciclista en la posición 3 y por lo tanto no es eliminado.
  • El ciclista en la posición 5 vence a los otros dos ciclistas y por lo tanto no es eliminado.
• En la ronda 3, la lista de ciclistas es [1, X, X, X, 4].
  • El ciclista en la posición 1 pierde contra los ciclistas en las posiciones 5 y 5 (que son el mismo ciclista) y es eliminado.
  • El ciclista en la posición 5 vence al ciclista en la posición 1 y por lo tanto no es eliminado.

Por lo tanto: El ciclista en la posición 1 fue eliminado en la ronda 3. El ciclista en la posición 2 fue eliminado en la ronda 1. El ciclista en la posición 3 fue eliminado en la ronda 2. El ciclista en la posición 4 fue eliminado en la ronda 1. * El ciclista en la posición 5 ganó la competición.

haciendo que la respuesta a la consulta sea [3, 1, 2, 1, 0].