时间限制： 每个测试 $2$ 秒
内存限制： 每个测试 $512$ MB

这是本题的困难版本。与简单版本的区别在于，本版本中你最多可以进行 $10 \cdot n$ 次查询。只有解决了所有版本的题目，你才能进行 hack。

阿里非常喜欢巴哈明的礼物（来自问题 E），以至于他非法从加兹温前往利物浦，想让足球运动员在礼物上签名。现在国际刑警正在追捕他，但他们提供了一个交易：解决一个问题，他就可以留在利物浦。但他现在在体育场里，无法解题——所以他请你来帮忙。

这是一道交互题。

有一个隐藏的排列 $p$，长度为 $n \ge 4$，且对于每个 $1 \le i \le n$，满足 $p_i \neq i$。

首先，你需要向评测机输出一个正整数 $k \le n$，该 $k$ 在之后的查询中保持不变。然后你需要通过若干次查询找出排列 $p$。

在每次查询中，你会向评测机给出一个排列 $q_1, q_2, \dots, q_n$。作为回应，你将收到满足以下所有条件的二元组 $(i, j)$ 的数量：

• $i < j$；
• $p_{q_i} = q_j$；
• $i \neq k$（$k$ 是你一开始提供给评测机的常数）。

给定 $n$，你需要在最多 $10 \cdot n$ 次查询内找出排列 $p$。

---

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 500$）。接下来是每个测试用例的描述。

每个测试用例只有一行，包含一个整数 $n$（$4 \le n \le 100$）—— 排列 $p$ 的长度。

保证所有测试用例的 $n^2$ 之和不超过 $10^4$。

---

交互方式
每个测试用例的交互从读取整数 $n$ 开始。

然后你需要输出整数 $k$（$1 \le k \le n$）。这不是一次查询。

然后你可以进行最多 $10 \cdot n$ 次查询。

要进行查询，按以下格式输出一行：

? q1 q2 ... qn

评测机将返回该查询的答案。

当你找到排列 $p$ 时，按以下格式输出一行：

! p1 p2 ... pn

这也不算作一次查询。

之后继续处理下一个测试用例，如果是最后一个测试用例则终止程序。

交互器不是自适应的，这意味着排列在选手输出 $k$ 之前就已经确定。

如果你的程序进行了超过 $10 \cdot n$ 次查询，你的程序应立即终止，以获得 Wrong answer 判决。否则你可能得到任意判决，因为你的程序会继续从已关闭的流中读取。

每次输出查询后，不要忘记输出换行符并刷新输出。否则你将收到 Idleness limit exceeded 判决。

如果在任何交互步骤中你读到了 $-1$ 而不是有效数据，你的程序必须立即退出。这意味着由于无效查询或其他错误，你的程序将收到 Wrong answer。不退出可能导致任意判决，因为你的程序会继续从已关闭的流中读取。

---

Hack 格式

要进行 hack，使用以下格式：

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 500$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$4 \le n \le 100$）—— 排列 $p$ 的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，$p_i \neq i$，所有 $p_i$ 互不相同）—— 排列 $p$。

保证所有测试用例的 $n^2$ 之和不超过 $10^4$。

---

刷新输出方式

• C++：fflush(stdout) 或 cout.flush()；
• Python：sys.stdout.flush()；
• 其他语言请查阅相关文档。

---

样例输入

2
4

1

5

1

2

样例输出

1
? 1 2 3 4

! 3 1 4 2

3
? 1 2 5 4 3

? 2 1 4 3 5

! 3 1 2 5 4

提示
在第一个测试用例中，$p = [3, 1, 4, 2]$。程序选择了 $k = 1$，然后查询了 $q = [1, 2, 3, 4]$。只有二元组 $(3, 4)$ 满足条件。

在第二个测试用例中，$p = [3, 1, 2, 5, 4]$。程序选择了 $k = 3$。

• 对于排列 $q = [1, 2, 5, 4, 3]$，只有 $(1, 5)$ 满足条件。
• 对于排列 $q = [2, 1, 4, 3, 5]$，$(1, 2)$ 和 $(2, 4)$ 满足条件。