Danke für deine harte Arbeit, Liebling. Little Cyan Fish weiß nicht, wie viele seiner Codewörter übermittelt werden können, dankt dir aber dennoch dafür, dass du bis zu diesem Punkt mit Little Cyan Fish gegangen bist. So viele Dinge, so viele absurde Dinge sind passiert, Little Cyan Fish ist müde, sehr müde... Im vergangenen Jahr hatte Little Cyan Fish mehrmals das Gefühl, er würde sich selbst retten, doch am Ende war er nicht stark genug, um die Fäden an seinem Körper zu durchtrennen. Little Cyan Fish stellt sich immer vor, dass es an jenem fernen Ort ein anderes Ich gibt, das die Karte seines Lebens klar erkennen kann.

— „Longing for the Distance“ · Finale des 10. China Collegiate Programming Contest

Dies ist ein interaktives Problem.

Nun, vielleicht kannst du versuchen herauszufinden, wie schwierig das sein wird. Little Cyan Fish hat das Gefühl, dass sein Leben eine Permutation unbekannter Gestalt ist. Die Leute sagen immer, die Welt sei voller Zufälligkeit, aber warum hat Little Cyan Fish immer so viel Pech...? Aha! Vielleicht ist die Zufälligkeit einfach so tiefgründig! Also beschließt Little Cyan Fish, dass diese seine Permutation auf folgende Weise zufällig erzeugt wird:

• Erzeuge eine zufällige Permutation $p_1, p_2, \dots, p_n$: gleichverteilt zufällig ausgewählt aus allen $n!$ möglichen Permutationen von $1$ bis $n$.
• Falls $p_1 > p_n$ gilt, kehre die gesamte Permutation um.

Du kannst die Struktur der Permutation nicht direkt beobachten, aber Little Cyan Fish hat dir eine Superkraft verliehen: Fragen stellen! Jedes Mal kannst du interaktiv den Wert des Abstands zwischen zwei Zahlen in der Permutation modulo $3$ abfragen. Genauer gesagt kannst du jedes Mal zwei Zahlen $u, v$ ($1 \le u, v \le n$, $u \ne v$) wählen, und die Permutation teilt dir den Wert des Abstands zwischen diesen beiden Zahlen modulo $3$ mit (d. h., sie findet zwei Indizes $i, j$ mit $p_i = u, p_j = v$ und antwortet mit $|i - j| \bmod 3$).

Nun möchte Little Cyan Fish, dass du es versuchst und siehst, was du erreichen kannst. Du musst Little Cyan Fish helfen, diese Permutation in höchstens $25n$ Abfragen zu bestimmen.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 1000$), die die Anzahl der Testfälle angibt.

Für jeden Testfall musst du zuerst eine ganze Zahl $n$ ($3 \le n \le 10^4$) einlesen.

Interaktionsprotokoll

Als Nächstes beginnt die Interaktion. Du darfst in jedem Testfall höchstens $25n$ Abfragen stellen. Um eine Abfrage zu stellen, musst du eine einzelne Zeile ? u v ($1 \le u, v \le n$, $u \ne v$) ausgeben, die eine Abfrage beschreibt. Anschließend musst du das Ergebnis von der Standardeingabe einlesen.

Um deine Antwort anzugeben, musst du ! p1 p2 ... pn ausgeben. Deine Ausgabe muss $p_1 < p_n$ erfüllen. Das Ausgeben der Antwort zählt nicht zum Limit von $25n$ Abfragen. Nachdem du die Antwort ausgegeben hast, musst du sofort den nächsten Testfall einlesen oder dein Programm sofort beenden.

Vergiss nach dem Ausgeben einer Abfrage nicht, einen Zeilenumbruch auszugeben und den Ausgabestrom zu leeren (flush). Dazu kannst du fflush(stdout) oder cout.flush() in C++, System.out.flush() in Java, flush(output) in Pascal und stdout.flush() in Python verwenden.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^4$ nicht überschreitet.

In diesem Problem wird garantiert, dass der Interaktor nicht-adaptiv ist. Das heißt, die Permutationen werden vor dem Interaktionsprozess wie im Problem beschrieben zufällig festgelegt. Sie ändern sich nicht in Abhängigkeit von deinen Abfragen. Es gibt insgesamt $30$ Testfälle (einschließlich des Beispieltestfalls).

Beispiel

Eingabe 1

2
3
2
1
1
4
1
1
1
0
2

Ausgabe 1

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

Hinweis

Abbildung 1: Little Cyan Fish & <?> bei <?>, aufgenommen am 4. März 2026