辛苦晒，親愛嘅。小青魚唔知佢嘅密碼可以傳達幾多，但係依然多謝你同小青魚一齊行到呢一步。 發生咗太多事，太多荒誕嘅事，小青魚攰喇，真係好攰……喺過去嘅一年入面，小青魚好幾次覺得自己喺度自救，但到頭來，佢仲未強大到可以斬斷身上嘅絲線。小青魚成日幻想，喺嗰個遙遠嘅地方，有另一個自己，可以清楚咁睇到佢生命嘅地圖。

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

呢個係一道交互題。

好啦，或者你可以試下，睇下呢個會有幾難。小青魚覺得佢嘅生活係一個形狀未知嘅排列。啲人成日話世界充滿咗隨機性，但點解小青魚總係咁黑仔……？啊！或者隨機性就係咁深奧！所以，小青魚決定佢嘅呢個排列將會透過以下方式隨機生成：

• 隨機生成一個排列 $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 日