Este es un problema interactivo.

VegiCat conoce un arreglo $a_1, a_2, \ldots, a_n$, donde cada elemento es $0$, $1$ o $2$. No quiere decirte sus valores, pero puedes hacerle preguntas. En cada consulta, eliges dos índices $i$ y $j$, y VegiCat te dice si $a_i > a_j$.

VegiCat te pide que imprimas los índices en orden no decreciente según los valores correspondientes del arreglo. Es decir, encuentra una permutación $p_1, p_2, \ldots, p_n$ de $1, 2, \ldots, n$ tal que

$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$

Puedes realizar a lo sumo $2n - 3$ consultas en cada caso de prueba.

El interactor es adaptativo. Esto significa que el arreglo no está fijado de antemano. El interactor garantiza que siempre existe al menos un arreglo con elementos en $\{0, 1, 2\}$ consistente con todas las respuestas dadas hasta el momento. Tu permutación final debe ser válida para todo arreglo consistente con todas las respuestas.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 250$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

Cada caso de prueba comienza con un entero $n$ ($2 \le n \le 500$), la longitud del arreglo.

La suma de $n$ en todos los casos de prueba no supera $500$.

Interacción

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

? i j

Aquí, $1 \le i, j \le n$. Después de cada consulta, lee un entero:

• $1$, si $a_i > a_j$;
• $0$, si $a_i \le a_j$.

Se permiten consultas con $i = j$ y consultas repetidas, y ambas se incluyen en el conteo de consultas.

Cuando hayas determinado el orden, imprime una línea con el siguiente formato:

! p_1 p_2 ... p_n

Cada índice de $1$ a $n$ debe aparecer exactamente una vez. Imprimir la respuesta no cuenta como una consulta.

Si tu respuesta es correcta, pasa al siguiente caso de prueba leyendo su $n$, o termina tu programa si este era el último caso de prueba. El interactor no envía una confirmación por separado después de una respuesta.

Después de imprimir cada consulta o respuesta, imprime un salto de línea y vacía el búfer de salida (flush). Para vaciar la salida, puedes usar:

• fflush(stdout) o cout.flush() en C/C++;
• System.out.flush() en Java y Kotlin;
• sys.stdout.flush() en Python.

Si realizas una consulta inválida, excedes el límite de consultas o imprimes una respuesta incorrecta, recibirás un veredicto de Wrong Answer. Una salida que no siga el formato especificado también será juzgada como Wrong Answer. En estos casos, el interactor termina sin enviar una respuesta de error.

Ejemplos

Entrada 1

2
3

1

1

2

0

Salida 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Nota

En el primer caso de prueba, las consultas ? 1 2 y ? 2 3 devuelven ambas $1$, por lo que $a_1 > a_2 > a_3$. Por lo tanto, $(3, 2, 1)$ es una respuesta correcta.

En el segundo caso de prueba, la consulta ? 1 2 devuelve $0$, por lo que $a_1 \le a_2$. Por lo tanto, $(1, 2)$ es una respuesta correcta.