题目描述

在一条水平的 $x$ 轴上，从左到右依次放置了 $N$ 个不同的点，编号为 $1,2,\ldots,N$。第 $i$ 个点的颜色为 $A_i$。

你想在这些点之间画若干条曲线，每条曲线连接两个点。作画必须满足以下限制：

• 颜色相同的两个点不能被一条曲线连接；
• 每条曲线必须画在 $x$ 轴上方。也就是说，曲线的内部点都满足 $y>0$，端点满足 $y=0$；
• 任意两条不同曲线不能有公共内部点，但可以共享端点。

例如，若有 $4$ 个点，点 $1,2$ 为红色，点 $3,4$ 为蓝色，则最多可以画 $3$ 条曲线，分别连接点 $1$ 与 $4$、点 $2$ 与 $3$、点 $2$ 与 $4$。若试图画 $4$ 条曲线，则一定会违反上述至少一条限制。

图示说明：在一条水平 $x$ 轴上从左到右放置 $4$ 个点，其中点 $1,2$ 为红色，点 $3,4$ 为蓝色；在轴上方画出三条内部互不相交的曲线，分别连接点 $(1,4)$、$(2,3)$、$(2,4)$。该图说明在这种情况下最多可以画出 $3$ 条曲线。

给定每个点的颜色，请构造一种方案，使得在不违反限制的前提下，画出的曲线数量尽可能多，并输出每条曲线连接的两个点。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来依次给出 $T$ 组测试数据。

对于每组测试数据：

第一行包含两个整数 $N,M$，分别表示点数和颜色数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，其中 $A_i$ 表示第 $i$ 个点的颜色。

输出格式

对于每组测试数据，首先输出一行一个整数 $K$，表示最多可以画出的曲线数量。

接下来输出 $K$ 行，每行输出两个整数 $u,v$，表示画一条连接点 $u$ 和点 $v$ 的曲线。

输出的所有曲线必须满足题目中的全部限制。如果存在多种最优方案，输出任意一种即可。

数据范围

• $1\le T\le 101$；
• $2\le N\le 200000$；
• $2\le M\le N$；
• $1\le A_i\le M$；
• 所有测试数据中 $N$ 的总和不超过 $200000$。

样例

输入

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

输出

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

样例说明

第一组测试数据中，可以画出 $3$ 条合法曲线。

第二组和第三组样例输出分别给出了对应的一种最优方案。由于本题允许输出任意一种最优方案，因此样例输出并不唯一。