呢道係一道交互題。

VegiCat 知道一個陣列 $a_1, a_2, \ldots, a_n$，入面每個元素都係 $0$、$1$ 或者 $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\}$ 嘅陣列同目前為止畀出嘅所有回答一致。你最後輸出嘅排列必須對每一個同所有回答一致嘅陣列都有效。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 250$），代表測試數據嘅組數。接住落嚟係各組測試數據嘅描述。

每組測試數據由一個整數 $n$（$2 \le n \le 500$）開始，代表陣列嘅長度。

所有測試數據入面 $n$ 嘅總和唔超過 $500$。

互動

如果要進行一次詢問，請按以下格式輸出一行：

? i j

呢度 $1 \le i, j \le n$。每次詢問之後，讀入一個整數：

• 如果 $a_i > a_j$，就係 $1$；
• 如果 $a_i \le a_j$，就係 $0$。

題目容許 $i = j$ 嘅詢問同埋重複詢問，而且都會計入詢問次數入面。

當你確定咗個順序之後，請按以下格式輸出一行：

! p_1 p_2 ... p_n

由 $1$ 到 $n$ 嘅每個下標都必須啱啱好出現一次。輸出答案唔會計入詢問次數。

如果你嘅答案啱咗，請讀入下一組測試數據嘅 $n$ 繼續做落去；如果呢組已經係最後一組測試數據，就結束你嘅程式。交互器喺收到答案之後唔會另外發送確認訊息。

每次輸出詢問或者答案之後，請輸出一個換行符同埋刷新輸出緩衝區。你可以用以下方法刷新輸出：

• 喺 C/C++ 入面用 fflush(stdout) 或者 cout.flush()；
• 喺 Java 同 Kotlin 入面用 System.out.flush()；
• 喺 Python 入面用 sys.stdout.flush()。

如果你作出咗唔合法嘅詢問、超過詢問次數上限，或者輸出咗錯嘅答案，你會得到 Wrong Answer 嘅結果。唔符合指定格式嘅輸出亦都會被判為 Wrong Answer。喺呢啲情況下，交互器會直接結束而唔會發送錯誤回應。

Examples

Input 1

2
3

1

1

2

0

Output 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Note

喺第一組測試數據入面，詢問 ? 1 2 同 ? 2 3 都返回 $1$，所以 $a_1 > a_2 > a_3$。因此，$(3, 2, 1)$ 係一個正確答案。

喺第二組測試數據入面，詢問 ? 1 2 返回 $0$，所以 $a_1 \le a_2$。因此，$(1, 2)$ 係一個正確答案。