C. 猜测树

• 每个测试的时间限制：2 秒
• 内存限制：256 MB

---

题目类型

这是一个 交互式问题。

---

题目描述

Misuki 选定了一棵有 $n$ 个节点的秘密树，节点编号为 $1$ 到 $n$。
你要通过以下类型的查询来猜测这棵树：

查询格式：? a b
Misuki 会告诉你一个节点 $x$，使得 $|d(a, x) - d(b, x)|$ 最小，其中 $d(x, y)$ 表示节点 $x$ 和 $y$ 之间的距离。
如果存在多个这样的节点 $x$，Misuki 会告诉你其中 $d(a, x)$ 最小的那个。

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

---

输入

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

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

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

---

交互过程

1. 首先读入 $n$。
2. 你可以进行最多 $15n$ 次查询。
3. 每次查询输出一行 ? a b（$1 \le a, b \le n$），然后读入一个整数，即查询的答案。
4. 当你要输出答案时，输出一行 !，然后按顺序输出 $n-1$ 条边，每条边由两个整数 $a_i$ 和 $b_i$ 表示。
   格式：! a1 b1 a2 b2 ... a_{n-1} b_{n-1}
   你可以以任意顺序输出这些边。

注意：

• 如果查询次数超过 $15n$，之后任何查询都会返回 $-1$。一旦收到 $-1$，应立即终止程序（否则会得到 Wrong Answer）。
• 每输出一行后，要刷新输出缓冲区（例如 cout.flush() 或 fflush(stdout)）。

---

输出示例

输入：

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)$。

---

黑客（Hack）格式

对于 hacks，输入格式如下：

• 第一行：$t$（$1 \le t \le 200$）
• 每个测试用例：
  • 第一行：$n$
  • 接下来 $n-1$ 行，每行两个整数 $a_i$ 和 $b_i$，表示秘密树的一条边。

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