Dies ist ein interaktives Problem.

VegiCat kennt ein Array $a_1, a_2, \ldots, a_n$, in dem jedes Element den Wert $0$, $1$ oder $2$ hat. Er möchte dir die Werte nicht verraten, aber du kannst ihm Fragen stellen. In jeder Anfrage wählst du zwei Indizes $i$ und $j$, und VegiCat teilt dir mit, ob $a_i > a_j$ gilt.

VegiCat bittet dich, die Indizes in nichtabsteigender Reihenfolge der zugehörigen Arraywerte auszugeben. Das heißt, finde eine Permutation $p_1, p_2, \ldots, p_n$ von $1, 2, \ldots, n$, sodass

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

Du darfst in jedem Testfall höchstens $2n - 3$ Anfragen stellen.

Der Interaktor ist adaptiv. Das bedeutet, dass das Array nicht im Voraus festgelegt ist. Der Interaktor garantiert, dass es immer mindestens ein Array mit Elementen aus $\{0, 1, 2\}$ gibt, das mit allen bisher gegebenen Antworten konsistent ist. Deine endgültige Permutation muss für jedes mit allen Antworten konsistente Array gültig sein.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 250$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Jeder Testfall beginnt mit einer ganzen Zahl $n$ ($2 \le n \le 500$), der Länge des Arrays.

Die Summe von $n$ über alle Testfälle überschreitet $500$ nicht.

Interaktion

Um eine Anfrage zu stellen, gib eine Zeile im folgenden Format aus:

? i j

Hierbei gilt $1 \le i, j \le n$. Lies nach jeder Anfrage eine ganze Zahl ein:

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

Anfragen mit $i = j$ sowie wiederholte Anfragen sind erlaubt und zählen zur Gesamtzahl der Anfragen hinzu.

Wenn du die Reihenfolge bestimmt hast, gib eine Zeile im folgenden Format aus:

! p_1 p_2 ... p_n

Jeder Index von $1$ bis $n$ muss genau einmal vorkommen. Das Ausgeben der Antwort zählt nicht als Anfrage.

Wenn deine Antwort korrekt ist, fahre mit dem nächsten Testfall fort, indem du dessen $n$ einliest, oder beende dein Programm, falls dies der letzte Testfall war. Der Interaktor sendet nach einer Antwort keine gesonderte Bestätigung.

Gib nach jeder Anfrage oder Antwort einen Zeilenumbruch aus und leere den Ausgabepuffer (flush). Zum Leeren des Ausgabepuffers kannst du Folgendes verwenden:

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

Falls du eine ungültige Anfrage stellst, das Anfragelimit überschreitest oder eine falsche Antwort ausgibst, erhältst du das Urteil Wrong Answer. Eine Ausgabe, die nicht dem angegebenen Format entspricht, wird ebenfalls als Wrong Answer gewertet. In diesen Fällen beendet sich der Interaktor, ohne eine Fehlermeldung zu senden.

Beispiele

Eingabe 1

2
3

1

1

2

0

Ausgabe 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Hinweis

Im ersten Testfall liefern die Anfragen ? 1 2 und ? 2 3 beide $1$, also gilt $a_1 > a_2 > a_3$. Daher ist $(3, 2, 1)$ eine korrekte Antwort.

Im zweiten Testfall liefert die Anfrage ? 1 2 den Wert $0$, also gilt $a_1 \le a_2$. Daher ist $(1, 2)$ eine korrekte Antwort.