これはインタラクティブな問題です。

VegiCat は配列 $a_1, a_2, \ldots, a_n$ を知っており、各要素は $0$, $1$, または $2$ です。彼はその値を直接教えてくれませんが、質問をすることができます。各質問では、2 つの添字 $i$ と $j$ を選び、VegiCat は $a_i > a_j$ かどうかを教えてくれます。

VegiCat は、対応する配列の値の非減少順に添字を出力するよう求めています。つまり、$1, 2, \ldots, n$ の順列 $p_1, p_2, \ldots, p_n$ であって、次を満たすものを見つけてください：

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

各テストケースにおいて、最大で $2n - 3$ 回の質問を行うことができます。

ジャッジ（インタラクタ）は適応的（adaptive）です。つまり、配列はあらかじめ固定されていません。インタラクタは、これまでに返したすべての返答と矛盾しない、要素が $\{0, 1, 2\}$ からなる配列が少なくとも 1 つ常に存在することを保証します。最終的な順列は、すべての返答と矛盾しないすべての配列に対して正しいものでなければなりません。

入力

1 行目にはテストケースの個数を表す整数 $T$（$1 \le T \le 250$）が与えられます。続いて各テストケースが与えられます。

各テストケースは、配列の長さを表す整数 $n$（$2 \le n \le 500$）から始まります。

すべてのテストケースにわたる $n$ の総和は $500$ を超えません。

インタラクション

質問を行うには、次の形式で 1 行出力してください：

? i j

ここで $1 \le i, j \le n$ です。各質問の後、整数を 1 つ読み込んでください：

• $a_i > a_j$ のとき $1$；
• $a_i \le a_j$ のとき $0$。

$i = j$ である質問や同じ質問の繰り返しも許可されており、それらも質問回数にカウントされます。

順序が特定できたら、次の形式で 1 行出力してください：

! p_1 p_2 ... p_n

$1$ から $n$ までの各添字がちょうど 1 回ずつ現れなければなりません。答えの出力は質問回数にはカウントされません。

答えが正しい場合、次のテストケースの $n$ を読み込んで次のテストケースに進むか、これが最後のテストケースであればプログラムを終了してください。インタラクタは答えの後に個別の確認応答を送りません。

各質問または答えを出力した後は、改行を出力して出力バッファをフラッシュしてください。出力をフラッシュするには、以下を使用できます：

• C/C++ では fflush(stdout) または cout.flush()；
• Java および Kotlin では System.out.flush()；
• Python では sys.stdout.flush()。

無効な質問を行った場合、質問回数の上限を超えた場合、または誤った答えを出力した場合は、Wrong Answer と判定されます。指定された形式に従わない出力も Wrong Answer と判定されます。これらの場合、インタラクタはエラー応答を送らずに終了します。

入出力例

入力 1

2
3

1

1

2

0

出力 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

注記

1 つ目のテストケースでは、質問 ? 1 2 と ? 2 3 がどちらも $1$ を返すため、$a_1 > a_2 > a_3$ です。したがって、$(3, 2, 1)$ は正しい答えです。

2 つ目のテストケースでは、質問 ? 1 2 が $0$ を返すため、$a_1 \le a_2$ です。したがって、$(1, 2)$ は正しい答えです。