お疲れ様、ダーリン。Little Cyan Fish は自分の暗号がどれだけ伝わるか分からないけれど、ここまで一緒に歩いてきてくれたことに感謝しているよ。 本当にたくさんのこと、あまりにも不条理なことが起きすぎて、Little Cyan Fish は疲れた、とても疲れてしまった……。この 1 年間、Little Cyan Fish は何度も自分を救おうとしていると感じたけれど、結局のところ、体に絡みついた糸を断ち切るほど強くはなかった。Little Cyan Fish はいつも、あの遥か彼方の場所に、自分の人生の地図をはっきりと見渡せるもう一人の自分がいると想像しているんだ。
——「彼方への憧れ」・第 10 回中国大学生プログラミングコンテスト決勝
これはインタラクティブな問題です。
さて、これがどれほど難しいか、試してみるといいかもしれません。Little Cyan Fish は、自分の人生は形も分からない順列のようなものだと感じています。世の中はランダム性に満ちているとよく言われますが、なぜ Little Cyan Fish はいつもこんなにも不運なのでしょうか……？ ああ！ きっとランダム性とはこれほどまでに奥深いものなのでしょう！ そこで Little Cyan Fish は、自身の順列を以下の方法でランダムに生成することにしました：
- ランダムな順列 $p_1, p_2, \dots, p_n$ を生成する：$1$ から $n$ までのあり得るすべての順列 $n!$ 通りの中から一様ランダムに選ぶ。
- もし $p_1 > p_n$ ならば、順列全体を反転させる。
順列の構造を直接観察することはできませんが、Little Cyan Fish はあなたに超能力を授けました。それは「質問すること」です！ 毎回、順列上の 2 つの数の距離を $3$ で割った余りをインタラクティブに質問できます。具体的には、毎回 2 つの数 $u, v$（$1 \le u, v \le n$、$u \ne v$）を選ぶと、順列はこれら 2 つの数の距離を $3$ で割った余りを教えてくれます（すなわち、$p_i = u, p_j = v$ を満たす 2 つのインデックス $i, j$ を見つけ、$|i - j| \bmod 3$ を返します）。
さあ、Little Cyan Fish はあなたに何が得られるか試してほしいと思っています。$25n$ 回以内の質問でこの順列を特定し、Little Cyan Fish を助けてください。
入力
複数のテストケースがあります。入力の 1 行目には、テストケースの個数を表す 1 つの整数 $T$（$1 \le T \le 1000$）が与えられます。
各テストケースについて、まず整数 $n$（$3 \le n \le 10^4$）を読み込む必要があります。
入出力プロトコル
続いて対話が始まります。各テストケースでは最大 $25n$ 回の質問を行うことができます。質問を行うには、質問を表す 1 行 ? u v（$1 \le u, v \le n$、$u \ne v$）を出力する必要があります。その後、標準入力から結果を読み込んでください。
答えを提出するには、! p1 p2 ... pn を出力する必要があります。出力は $p_1 < p_n$ を満たさなければなりません。答えの出力は $25n$ 回の質問制限にはカウントされません。答えを出力した後は、ただちに次のテストケースを読み込むか、プログラムを即座に終了してください。
質問を出力した後、改行文字を出力し、出力ストリームをフラッシュすることを忘れないでください。これを行うには、C++ では fflush(stdout) または cout.flush()、Java では System.out.flush()、Pascal では flush(output)、Python では stdout.flush() を使用できます。
すべてのテストケースにおける $n$ の総和は $10^4$ を超えないことが保証されます。
この問題では、ジャッジ（インタラクタ）は非適応的（non-adaptive）であることが保証されます。つまり、順列は対話プロセスの前に問題文で述べられた通りにランダムに決定されており、あなたの質問に応じて変化することはありません。テストケースは（サンプルを含めて）合計 $30$ 個あります。
入出力例
入力例 1
2 3 2 1 1 4 1 1 1 0 2
出力例 1
? 1 2 ? 2 3 ? 1 3 ! 1 3 2 ? 2 3 ? 3 1 ? 1 4 ? 2 4 ? 2 1 ! 2 3 1 4
注記
図 1：2026 年 3 月 4 日に <?> で撮影された Little Cyan Fish と <?>