C. 猜树
时间限制：每个测试点 $2$ 秒
内存限制：$256$ 兆字节

这是一个交互式问题。

Misuki 选择了一棵 $n$ 个节点的秘密树，节点编号为 $1$ 到 $n$，要求你通过如下类型的查询来猜出它：

• "? a b" —— Misuki 会告诉你一个节点 $x$，它最小化 $|d(a, x) - d(b, x)|$，其中 $d(x, y)$ 是节点 $x$ 与节点 $y$ 之间的距离。如果存在多个这样的节点，Misuki 会告诉你其中 $d(a, x)$ 最小的那个。

请在最多 $15n$ 次查询内找出 Misuki 秘密树的结构。

输入格式
每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 200$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 1000$），表示树中节点的数量。

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

交互流程
交互从读入整数 $n$ 开始。

然后你可以进行最多 $15n$ 次查询。
每次查询输出一行 "? a b"（不含引号，$1 \le a, b \le n$）。查询后读入一个整数，即查询的答案。

要输出答案，输出一行 "! a1 b1 a2 b2 ... a_{n-1} b_{n-1}"（不含引号），表示第 $i$ 条边连接节点 $a_i$ 和 $b_i$，$1 \le i \le n-1$。你可以以任意顺序输出边。

如果在 $15n$ 次查询后继续查询，会收到 $-1$。一旦收到这样的响应，立即终止程序（否则会判为 Wrong Answer）。

输出每行后不要忘记输出换行并刷新输出缓冲区。否则你会收到 Idleness limit exceeded。
刷新缓冲区的方法：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其他语言请参考文档。

Hack 格式
对于 Hack，请使用以下格式：
第一行包含一个整数 $t$（$1 \le t \le 200$）——测试用例数量。
每个测试用例的第一行包含一个整数 $n$。
接下来 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示秘密树中的一条边。
所有测试用例的 $n$ 之和不得超过 $1000$。

样例输入

1
4
1
1
3

样例输出

? 1 2

? 1 3

? 1 4

! 1 2 1 3 3 4

样例解释
树是无向无环连通图，$n$ 个节点的树总是有 $n-1$ 条边。

在样例中：

• 对 ? 1 2 的答案是 $1$，说明节点 $1$ 和 $2$ 之间有边。
• 对 ? 1 3 的答案是 $1$，说明节点 $1$ 和 $3$ 之间有边。
• 对 ? 1 4 的答案是 $3$，可以证明只有在节点 $3$ 同时连接节点 $1$ 和 $4$ 时才会出现这个答案。

因此树的边为 $(1,2)$、$(1,3)$ 和 $(3,4)$。