這是一道互動題。

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。在這些情況下，互動器會直接結束，而不會發送錯誤回應。

範例

輸入格式 1

2
3

1

1

2

0

輸出格式 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

說明

在第一組測試資料中，詢問 ? 1 2 和 ? 2 3 均回傳 $1$，因此 $a_1 > a_2 > a_3$。所以 $(3, 2, 1)$ 是一個正確答案。

在第二組測試資料中，詢問 ? 1 2 回傳 $0$，因此 $a_1 \le a_2$。所以 $(1, 2)$ 是一個正確答案。