辛苦了，親愛的。小青魚不知道他的密碼能傳達多少，但依然感謝你和小青魚一起走到這裡。 發生了太多事，太多荒誕的事，小青魚累了，真的很累……在過去的一年裡，小青魚好幾次覺得自己在自救，但終究，他還沒有強大到可以斬斷身上的絲線。小青魚總是幻想，在那個遙遠的地方，有另一個自己，能清晰地看到他生命的地圖。

—— 「嚮往彼方」· 第十屆中國大學生程式設計競賽總決賽

這是一道互動題。

好吧，也許你可以嘗試一下，這會有多少難度。小青魚覺得他的生活是一個形狀未知的排列。人們總是說世界充滿了隨機性，但為什麼小青魚總是這麼倒楣……？啊！也許隨機性就是如此深奧！所以，小青魚決定他的這個排列將透過以下方式隨機生成：

• 隨機生成一個排列 $p_1, p_2, \dots, p_n$：從 $1$ 到 $n$ 的所有 $n!$ 種可能排列中等機率均勻隨機選擇。
• 如果 $p_1 > p_n$，則翻轉整個排列。

你無法直接觀察到排列的結構，但小青魚賦予了你一種超能力：詢問！每次你可以互動式地查詢排列中兩個數之間距離模 $3$ 的值。具體來說，每次你可以選擇兩個數 $u, v$（$1 \le u, v \le n$，$u \ne v$），系統會告訴你這兩個數在排列中位置距離模 $3$ 的值（即找到滿足 $p_i = u, p_j = v$ 的兩個下標 $i, j$，系統將回答 $|i - j| \bmod 3$）。

現在，小青魚想讓你嘗試一下，看看你能得到什麼。你需要幫助小青魚在不超過 $25n$ 次詢問內確定這個排列。

輸入格式

包含多組測試資料。輸入的第一行包含一個整數 $T$（$1 \le T \le 1000$），表示測試用例的數量。

對於每個測試用例，首先你需要讀取一個整數 $n$（$3 \le n \le 10^4$）。

互動協定

接下來開始互動。在每個測試用例中，你最多可以進行 $25n$ 次詢問。要進行詢問，你需要輸出單行 ? 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 日