这是一个交互式问题。

Little Cyan Fish 是一位热衷于旅行的探险家，他正在探索一个由 $n$ 个城市组成的世界，城市编号从 $1$ 到 $n$。他从城市 $1$ 出发，希望绘制出连接这些城市的所有 $m$ 条双向道路。保证通过这些道路可以到达任何城市。此外，每条道路连接两个不同的城市，且任意两个城市之间最多只有一条道路。换句话说，这些城市和道路可以看作一个简单连通无向图。然而，由于没有地图，Little Cyan Fish 不知道这些道路的存在，因此他完全不知道这个世界中哪些道路是存在的。因此，他的目标是找到所有道路的信息。

为了实现这一目标，Little Cyan Fish 可以在这个世界中行走。当他站在某个城市时，Little Cyan Fish 可以看到当前城市的编号 $x$ 以及连接到城市 $x$ 的道路数量 $d_x$。然后，他可以选择通过从城市 $x$ 出发的第 $i$ 条道路（$1 \le i \le d_x$）进行行走。每个城市出发的道路顺序是未知的，但却是固定的。行走后，Little Cyan Fish 将站在他所选道路的另一个端点，并向你报告新城市的信息，即它的编号和连接到该城市的道路数量。

你的目标是帮助 Little Cyan Fish 通过重复上述过程找到所有的道路。由于 Little Cyan Fish 的时间有限，且环球旅行会消耗大量时间，他最多只能行走 $2m + 2n$ 次。请帮助他！

交互

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

对于每个测试用例，你不会预先知道 $n$ 和 $m$ 的确切值——交互过程立即开始。保证 $1 \le n \le 2500$ 且 $1 \le m \le 10^4$。

在交互的每一轮中，交互器将提供当前城市编号 $x$ 以及连接到城市 $x$ 的道路数量 $d_x$。若要进行一次行走，你需要在一行中打印 “> i” ($1 \le i \le d_x$)，表示你希望通过连接城市 $x$ 的第 $i$ 条道路进行行走。之后，新一轮交互开始，交互器将提供新的城市编号和连接到该城市的道路数量。你进行的查询次数不得超过 $2m + 2n$。

要给出你的答案，你需要打印 “! $x_1$ $y_1$ $x_2$ $y_2$ $\dots$ $x_m$ $y_m$”，表示你找到的所有道路。边的顺序可以是任意的，你只需要提供一种可能的方案即可。打印答案不被视为查询，也不计入 $2m + 2n$ 的限制。

在你提交答案后，如果你正确找到了所有 $m$ 条道路，交互器将打印一行 Correct，随后立即进入下一个测试用例。否则，如果你找到的 $m$ 条道路不正确，交互器将打印一行 Wrong，交互过程将被终止。如果你找到的道路少于 $m$ 条，交互器将等待你打印更多的边。这可能会导致 “Idleness Limit Exceeded”。

在打印查询后，请务必输出换行符并刷新缓冲区。为此，请在 C++ 中使用 fflush(stdout) 或 cout.flush()，在 Java 中使用 System.out.flush()，在 Pascal 中使用 flush(output)，或在 Python 中使用 stdout.flush()。

保证隐藏的图是简单且连通的，所有测试用例的 $n$ 之和不超过 $10^4$，所有测试用例的 $m$ 之和不超过 $4 \times 10^4$。

该问题的交互器是非自适应的，这意味着图是预先确定的，不会根据交互过程而改变。

样例

输入 1

2
1 1
2 1
1 1
Correct
1 3
2 2
1 3
2 2
4 2
1 3
3 1
Correct

输出 1

> 1
> 1
! 1 2
> 3
> 1
> 3
> 2
> 2
> 2
! 1 2 1 3 1 4 2 4