Grazie per il tuo duro lavoro, tesoro. Little Cyan Fish non sa quante delle sue parole in codice possano essere trasmesse, ma ti ringrazia comunque per aver camminato fino a questo punto insieme a Little Cyan Fish. Sono successe così tante cose, così tante cose assurde; Little Cyan Fish è stanco, molto stanco... Nell'ultimo anno, Little Cyan Fish ha sentito più volte che stava per salvarsi da solo, ma dopotutto non era abbastanza forte da tagliare i fili sul suo corpo. Little Cyan Fish immagina sempre che in quel luogo lontano ci sia un altro sé capace di vedere chiaramente la mappa della propria vita.

— "Longing for the Distance" · Finale del 10° China Collegiate Programming Contest

Questo è un problema interattivo.

Beh, forse puoi provare a vedere quanto sarà difficile. Little Cyan Fish sente che la sua vita è una permutazione dalla forma sconosciuta. La gente dice sempre che il mondo è pieno di casualità, ma perché Little Cyan Fish è sempre così sfortunato...? Aha! Forse la casualità è proprio così profonda! Così, Little Cyan Fish decide che questa sua permutazione verrà generata casualmente nel modo seguente:

• Genera una permutazione casuale $p_1, p_2, \dots, p_n$: scelta uniformemente a caso tra tutte le $n!$ possibili permutazioni da $1$ a $n$.
• Se $p_1 > p_n$, allora inverti l'intera permutazione.

Non puoi osservare direttamente la struttura della permutazione, ma Little Cyan Fish ti ha concesso un superpotere: fare domande! Ogni volta, puoi chiedere in modo interattivo il valore della distanza tra due numeri nella permutazione modulo $3$. Nello specifico, ogni volta puoi scegliere due numeri $u, v$ ($1 \le u, v \le n$, $u \ne v$), e la permutazione ti dirà il valore della distanza tra questi due numeri modulo $3$ (cioè, trovando due indici $i, j$ che soddisfano $p_i = u, p_j = v$, la permutazione risponderà $|i - j| \bmod 3$).

Ora, Little Cyan Fish vuole che tu provi a vedere cosa riesci a ottenere. Devi aiutare Little Cyan Fish a determinare questa permutazione in non più di $25n$ query.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 1000$), che indica il numero di casi di test.

Per ogni caso di test, per prima cosa devi leggere un intero $n$ ($3 \le n \le 10^4$).

Protocollo di interazione

Successivamente, inizia l'interazione. Puoi effettuare non più di $25n$ query in ogni caso di test. Per effettuare una query, devi stampare una singola riga ? u v ($1 \le u, v \le n$, $u \ne v$), che descrive una query. Quindi, devi leggere il risultato dallo standard input.

Per fornire la tua risposta, devi stampare ! p1 p2 ... pn. Il tuo output deve soddisfare $p_1 < p_n$. La stampa della risposta non verrà conteggiata nel limite di $25n$ query. Dopo aver stampato la risposta, devi leggere immediatamente il caso di test successivo, oppure terminare immediatamente il programma.

Dopo aver stampato una query, non dimenticare di stampare un carattere di ritorno a capo e di svuotare il buffer di output (flush). Per farlo, puoi usare fflush(stdout) o cout.flush() in C++, System.out.flush() in Java, flush(output) in Pascal e stdout.flush() in Python.

È garantito che la somma di $n$ su tutti i casi di test non supera $10^4$.

In questo problema, è garantito che l'interattore sia non adattivo. Cioè, le permutazioni vengono determinate casualmente come descritto nel problema prima del processo di interazione. Non cambieranno in base alle tue query. Ci sono in totale $30$ casi di test (incluso il caso di test di esempio).

Esempio

Input 1

2
3
2
1
1
4
1
1
1
0
2

Output 1

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

Note

Figura 1: Little Cyan Fish & <?> presso <?> scattata il 4 marzo 2026