Questo è un problema interattivo.

VegiCat conosce un array $a_1, a_2, \ldots, a_n$, in cui ogni elemento vale $0$, $1$ oppure $2$. Non vuole dirti i suoi valori, ma puoi fargli delle domande. In ogni query scegli due indici $i$ e $j$, e VegiCat ti dice se $a_i > a_j$.

VegiCat ti chiede di stampare gli indici in ordine non decrescente rispetto ai corrispondenti valori dell'array. Cioè, trova una permutazione $p_1, p_2, \ldots, p_n$ di $1, 2, \ldots, n$ tale che

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

Puoi effettuare al massimo $2n - 3$ query in ciascun caso di test.

L'interattore è adattivo. Ciò significa che l'array non è fissato in anticipo. L'interattore garantisce che esiste sempre almeno un array con elementi in $\{0, 1, 2\}$ coerente con tutte le risposte fornite fino a quel momento. La tua permutazione finale deve essere valida per ogni array coerente con tutte le risposte.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 250$), il numero di casi di test. Segue la descrizione dei casi di test.

Ogni caso di test inizia con un intero $n$ ($2 \le n \le 500$), la lunghezza dell'array.

La somma di $n$ su tutti i casi di test non supera $500$.

Interazione

Per effettuare una query, stampa una riga nel seguente formato:

? i j

Qui, $1 \le i, j \le n$. Dopo ogni query, leggi un intero:

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

Le query con $i = j$ e le query ripetute sono consentite e vengono conteggiate nel numero di query.

Quando hai determinato l'ordine, stampa una riga nel seguente formato:

! p_1 p_2 ... p_n

Ogni indice da $1$ a $n$ deve comparire esattamente una volta. Stampare la risposta non conta come una query.

Se la tua risposta è corretta, procedi al caso di test successivo leggendo il suo $n$, oppure termina il programma se questo era l'ultimo caso di test. L'interattore non invia una conferma separata dopo una risposta.

Dopo aver stampato ogni query o risposta, stampa un carattere di nuova riga ed esegui il flush del buffer di output. Per eseguire il flush dell'output puoi usare:

• fflush(stdout) oppure cout.flush() in C/C++;
• System.out.flush() in Java e Kotlin;
• sys.stdout.flush() in Python.

Se effettui una query non valida, superi il limite di query o stampi una risposta errata, riceverai il verdetto Wrong Answer. Anche un output che non rispetta il formato specificato viene giudicato Wrong Answer. In questi casi, l'interattore termina senza inviare una risposta di errore.

Examples

Input 1

2
3

1

1

2

0

Output 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Note

Nel primo caso di test, le query ? 1 2 e ? 2 3 restituiscono entrambe $1$, quindi $a_1 > a_2 > a_3$. Pertanto, $(3, 2, 1)$ è una risposta corretta.

Nel secondo caso di test, la query ? 1 2 restituisce $0$, quindi $a_1 \le a_2$. Pertanto, $(1, 2)$ è una risposta corretta.