这是一个交互式问题。

你曾经有一个大小为 $n$ 的排列 $\pi$。但现在它丢失了。你只剩下一个在学习群论时制作的旧设备。为了尝试恢复 $\pi$，你可以向该设备输入一个大小为 $n$ 的排列 $f$。然后，该设备将显示排列 $\pi^{-1} \circ f \circ \pi$。请在最多与设备进行两次交互的情况下找到 $\pi$。

大小为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个不同整数组成的序列。两个排列 $a$ 和 $b$ 的复合是一个排列 $a \circ b$，满足 $(a \circ b)_i = b_{a_i}$。也就是说，如果我们把排列看作是对 $n$ 个元素的操作，将位置 $i$ 的元素移动到 $a_i$，那么 $a \circ b$ 就是先应用 $a$，再应用 $b$ 的操作，使得位置 $i$ 的元素首先移动到 $a_i$，然后移动到 $b_{a_i}$。请注意，某些复合的定义使用的是相反的顺序。

逆排列 $\pi^{-1}$ 是满足 $\sigma_{\pi_i} = i$ 的排列 $\sigma$。一个排列与其逆排列的复合等于恒等排列：对于所有从 $1$ 到 $n$ 的 $i$，$(\pi \circ \pi^{-1})_i = (\pi^{-1} \circ \pi)_i = i$。例如，如果 $a = (4, 1, 3, 2)$ 且 $b = (3, 2, 1, 4)$，那么 $a \circ b = (4, 3, 1, 2)$，$a^{-1} = (2, 4, 3, 1)$ 且 $a^{-1} \circ b \circ a = (1, 2, 4, 3)$。

交互

您的程序必须在单次运行中处理多个测试用例。首先，测试系统会写入 $t$，即测试用例的数量（$t \ge 1$）。然后，应该逐个处理 $t$ 个测试用例。

在每个测试用例中，您的程序应首先读取整数 $n$（$3 \le n \le 10^4$），即排列 $\pi$ 的大小。所有测试用例中 $n$ 的总和不超过 $10^4$。然后，您的程序可以进行以下两种类型的查询：

• ? $f_1\ f_2\ \dots\ f_n$，其中值 $f_1, f_2, \dots, f_n$ 构成 $1, 2, \dots, n$ 的一个排列。测试系统会返回一个排列 $g_1, g_2, \dots, g_n$，其中 $g = \pi^{-1} \circ f \circ \pi$。
• ! $\pi_1\ \pi_2\ \dots\ \pi_n$ —— 您对秘密排列的猜测。

在每个测试用例中，您最多可以使用两次第一种类型的查询。在您的程序进行第二种类型的查询后，它应该继续处理下一个测试用例（如果该测试用例是最后一个，则退出）。

样例

输入样例 1

2
4
1 2 4 3
2 4 3 1
3
3 1 2
2 3 1

输出样例 1

? 3 2 1 4
? 2 4 3 1
! 4 1 3 2
? 2 3 1
? 3 1 2
! 3 2 1

说明

在第一个测试中共有两个测试用例。在第一个测试用例中，$\pi = (4, 1, 3, 2)$ 是唯一满足 $\pi^{-1} \circ (3, 2, 1, 4) \circ \pi = (1, 2, 4, 3)$ 且 $\pi^{-1} \circ (2, 4, 3, 1) \circ \pi = (2, 4, 3, 1)$ 的排列。在第二个测试用例中，根据交互，$\pi$ 可以是 $(1, 3, 2)$、$(2, 1, 3)$ 或 $(3, 2, 1)$ 中的任意一个。该程序运气较好，猜中了正确的一个：$(3, 2, 1)$。