在一场与无情敌人的殊死搏斗中……

这是一个交互式问题。

作为对抗强大邪恶帝国的精英间谍，你被指派了 $T$ 个独立的侦察任务。每个任务都在帝国的一个不同城市中进行，你的成功对反抗军至关重要。

每个城市由 $N$ 个关键建筑表示，编号为 $1$ 到 $N$，它们由道路网络连接。每条道路连接两个不同的建筑，同一对建筑之间可能存在多条道路。你在每个任务中的目标是完全重建该城市的道路网络。

为了实现这一目标，你配备了一个特殊设备，能够对城市的电网进行顺序断电。你可以定义一个断电序列 $p_1, p_2, \dots, p_N$ —— 所有 $N$ 个建筑的一个排列。在建筑 $p_i$ 被断电的准确时刻，该设备会报告连接 $p_i$ 与其他仍有电的建筑的道路数量。

在每个任务中，你最多可以使用该设备 $N - 1$ 次。

交互

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。

对于每个测试用例，交互以标准输入给出的单个整数 $N$（建筑数量）开始。

随后，你的程序可以通过进行顺序断电来探索城市的道路网络。为此，你可以发出如下格式的查询：

• ? p1 p2 ... pN — 使用你选择的断电序列 $p_1, \dots, p_N$ 启动一次断电。

作为对该查询的响应，你的程序将通过标准输入接收到包含 $N$ 个空格分隔整数 $c_1, c_2, \dots, c_N$ 的单行。这里 $c_i$ 是在建筑 $p_i$ 断电时刻测得的数据：即连接 $p_i$ 与其他仍有电的建筑的道路数量。

每个测试用例中，你最多可以进行 $N - 1$ 次顺序断电。

一旦你完成了任务并绘制出了整个道路网络，你必须报告你的发现。首先，打印一行以下格式的内容：

• ! M

其中 $M$ 是你发现的道路总数。

接下来，在随后的 $M$ 行中，打印两个空格分隔的整数 $u$ 和 $v$，表示在建筑 $u$ 和 $v$ 之间发现的一条道路。如果同一对建筑之间存在多条道路，你必须多次打印该对建筑。道路可以以任何顺序打印；任何顺序都是可以接受的。

交互器是非自适应的（non-adaptive）：每个城市的道路网络都是预先确定的，不依赖于你的查询。

数据范围

• $1 \le T \le 1000$
• $2 \le N \le 1000$
• $0 \le M \le 10^4$
• 所有测试用例的 $N$ 之和不超过 $2000$。
• 所有测试用例的 $M$ 之和不超过 $10^4$。

样例

输入格式 1

2
3
2 1 0
2 1 0
5
5 1 0 0 0
2 3 1 0 0

输出格式 1

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

说明

在打印每个查询后，你必须刷新输出缓冲区以确保交互器收到你的输出。否则可能会导致未知的评测结果。你可以使用以下方法刷新输出：

• 在 C++ 中，调用 fflush(stdout) 或 cout.flush()。
• 在 Java 中，调用 System.out.flush()。
• 在 Python 中，调用 sys.stdout.flush()。
• 在 Kotlin 中，调用 System.out.flush()。

对于其他语言，请参阅该语言的官方文档。