辛苦了，亲爱的。小青鱼不知道他的密码能传达多少，但依然感谢你和小青鱼一起走到这里。 发生了太多事，太多荒诞的事，小青鱼累了，真的很累……在过去的一年里，小青鱼好几次觉得自己在自救，但终究，他还没有强大到可以斩断身上的丝线。小青鱼总是幻想，在那个遥远的地方，有另一个自己，能清晰地看到他生命的地图。

—— “向往彼方” · 第十届中国大学生程序设计竞赛总决赛

这是一个交互式问题。

好吧，也许你可以尝试一下，这会有多难。小青鱼觉得他的生活是一个形状未知的排列。人们总是说世界充满了随机性，但为什么小青鱼总是这么倒霉……？啊！也许随机性就是如此深奥！所以，小青鱼决定他的这个排列将通过以下方式随机生成：

• 随机生成一个排列 $p_1, p_2, \dots, p_n$：从 $1$ 到 $n$ 的所有 $n!$ 种可能排列中等概率均匀随机选择。
• 如果 $p_1 > p_n$，则翻转整个排列。

你无法直接观察到排列的结构，但小青鱼赋予了你一种超能力：询问！每次你可以交互式地查询排列中两个数之间距离模 3 的值。具体来说，每次你可以选择两个数 $u, v$（$1 \le u, v \le n$ 且 $u \neq 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 \neq 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 日