考虑 $Ox$ 轴上有 $N$ 个不同的点，从左到右编号为 $1, 2, \dots, N$。每个点都有一个颜色：点 $i$ 的颜色为 $A_i$。

你想要画出若干条曲线，每条曲线连接两个点。然而，需要满足以下限制：

• 不能连接两个颜色相同的点。
• 每条连接点的曲线必须位于 $x$ 轴上方。换句话说，每条曲线的每个内部点都满足 $y > 0$。（端点满足 $y = 0$。）
• 两条不同的曲线不能有公共的内部点。（可以共享端点。）

例如，如果有 4 个点如下图所示，点 1 和 2 是红色的，点 3 和 4 是蓝色的，你可以画出总共 3 条曲线：连接点 1 和 4，点 2 和 3，以及点 2 和 4。

画 4 条曲线会违反上述至少一个限制，因此在这种情况下，最大数量为 3。

给定每个点的颜色，找出一种画出尽可能多连接两个点的曲线的方法，且不违反任何限制，并输出每条曲线连接的两个点。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量（$1 \le T \le 101$）。接下来是各个测试用例。 每个测试用例的第一行包含点数 $N$ 和颜色数 $M$（$2 \le N \le 200\,000$，$2 \le M \le N$）。 下一行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le M$）。 所有测试用例的 $N$ 之和不超过 $200\,000$。

输出格式

对于每个测试用例，首先输出一行，包含一个整数 $K$：连接两个点的最大曲线数量。 在接下来的 $K$ 行中，每行输出由一条曲线连接的两个点的编号。曲线必须满足上述所有限制。如果存在多种可能的答案，输出其中任意一种即可。

样例

输入 1

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

输出 1

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