这是一道交互题。

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)$ 是一个正确答案。