这是一个交互式问题。

Prof. Chen 精通计算几何和交互式问题。在教授了关于多边形三角剖分（polygon triangulation）† 的课程后，Prof. Chen 布置了以下家庭作业。

有一个正 $n$ 边形，其顶点按逆时针方向标记为 $1, 2, \dots, n$。存在一个由 $n-3$ 条连接顶点的边组成的隐藏三角剖分。你可以进行以下查询：

• “? $u$ $v$”：查询关于连接 $u$ 和 $v$ 的边的信息。如果边 $u-v$ 存在于三角剖分中，它将返回 0。否则，它将返回三角剖分中与 $(u, v)$ 在非端点处相交的边的数量。

你的任务是使用不超过 $n-3$ 次查询来确定这个三角剖分。

在本题中，交互器是非自适应的，这意味着三角剖分是预先确定的，并且在你的交互过程中不会改变。

†：在计算几何中，多边形三角剖分是将一个简单多边形 $P$ 分割成一组三角形，即找到一组内部互不相交且并集为 $P$ 的三角形。

图 1：所有 42 种七边形三角剖分的示意图（改编自 Wikipedia，CC BY-SA 3.0）。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 2500$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($4 \le n \le 100$)，表示该多边形是一个正 $n$ 边形。

保证所有 $n$ 的总和不超过 $10^4$。

交互

对于每个测试用例，你最多可以进行 $n-3$ 次查询。要进行查询，请在单独的一行中输出 “? $u$ $v$” ($1 \le u \neq v \le n$，$u$ 和 $v$ 在凸多边形上不相邻)，然后从标准输入读取响应。作为对查询的响应，交互器将返回一个整数 $x$，表示查询的结果。如果 $x = -1$，则意味着你的查询无效或超过了允许的查询次数，你应该终止程序，这将导致 Wrong Answer 判决。

当你准备好提交答案时，在单独的一行中输出 “! $a_1$ $b_1$ $a_2$ $b_2$ $\dots$ $a_{n-3}$ $b_{n-3}$”，表示三角剖分中的边为 $(a_i, b_i)$，其中 $1 \le i \le n-3$。提交答案不计入 $n-3$ 次查询的限制。作为对你答案的响应，交互器将返回一个整数 $r$。如果 $r = 1$，则意味着你的答案正确；如果 $r = 0$，则意味着你的答案不正确，你应该终止程序，这将导致 Wrong Answer 判决。

提交答案后，你的程序应继续处理下一个测试用例。一旦所有测试用例处理完毕，你的程序应终止。

在打印查询或提交答案后，不要忘记输出换行符并刷新输出。在 C++ 中使用 fflush(stdout) 或 cout.flush()，在 Java 中使用 System.out.flush()，或在 Python 中使用 stdout.flush()。

样例

输入 1

2
4
0
1
6
2
0
1

输出 1

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