题目描述

这是一个交互式问题。

Kevin 有 $n$ 个同学，编号为 $1, 2, \dots, n$。任意两人之间要么是朋友，要么不是朋友。

Kevin 想要选出 $2k$ 个同学组成 $k$ 个队伍，每个队伍恰好包含 $2$ 个人。每个人最多只能属于一个队伍。

设 $u_i$ 和 $v_i$ 为第 $i$ 个队伍中的两个人。为了避免组队过程中的潜在冲突，队伍成员必须满足以下两个条件之一：

• 对于所有 $i$ ($1 \le i \le k$)，同学 $u_i$ 和 $v_i$ 是朋友。
• 对于所有 $i$ ($1 \le i \le k$)，同学 $u_i$ 和 $v_i$ 不是朋友。

Kevin 想要确定最大的 $k$，使得无论这 $n$ 个人之间的友谊关系如何，他总能找到 $2k$ 个人来组成这些队伍。确定 $k$ 后，他需要给出这 $k$ 个队伍。但是，询问两个同学是否是朋友比较尴尬，因此 Kevin 希望在询问不超过 $n$ 对同学的友谊状态的情况下完成任务。

交互器是自适应的。这意味着同学之间的隐藏关系在交互开始前并未固定，并且会在交互过程中发生变化。

交互

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是各个测试用例的描述。

每个测试用例的第一行包含一个正整数 $n$ ($2 \le n \le 10^5$)，表示同学的数量。

首先，你应该输出一个整数 $k$ ($1 \le k \le \frac{n}{2}$)，表示你能组成的队伍的最大数量。

你可以通过以下方式进行询问：打印一行格式为 ? u v 的内容，其中 $1 \le u \neq v \le n$。之后，读取一个整数：$0$ 或 $1$，表示他们是否是朋友。$1$ 表示他们是朋友，$0$ 表示他们不是朋友。

如果你想输出答案，请输出 ! u1 v1 u2 v2 ... uk vk。你需要输出恰好 $2k$ 个不同的数字。然后，交互将继续进行下一个测试用例。

你最多可以进行 $n$ 次询问。打印答案不计入询问次数。

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

在打印每次询问后，请务必输出换行并刷新输出。否则，你将收到 Idleness limit exceeded 判决。

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

样例

样例输入 1

2
3
1
5
1
0
1
0
0

样例输出 1

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

说明

在第一个测试用例中： Kevin 声称无论 3 个人之间的友谊关系如何，他都能组成 1 个队伍。 Kevin 询问了 1 号和 2 号之间的友谊关系。裁判回答他们是朋友。 Kevin 回答他可以用 1 号和 2 号组成一个队伍。

在第二个测试用例中： Kevin 声称无论 5 个人之间的友谊关系如何，他都能组成 2 个队伍。 Kevin 询问了 (1, 2), (3, 4), (3, 5), (1, 3), (2, 4) 之间的友谊关系。裁判回答 1, 0, 1, 0, 0。 Kevin 回答他可以用 (1, 2) 和 (3, 5) 组成两个队伍。 也可以用 (1, 3) 和 (2, 4) 组成两个队伍，因为他们都不是朋友。