大流士大帝正在建造 $$$n$$$ 石柱,每根石柱都由一个基座和堆叠在顶部的 $$$0$$$、$$$1$$$ 或 $$$2$$$ 铭文组成。
在每次移动中,Darius 可以选择两列 $$$u$$$ 和 $$$v$$$,使得这些列之间的铭文数量差异恰好为 $$$1$$$,并将一个铭文从铭文较多的列转移到另一列。保证至少一列恰好包含 $$$1$$$ 铭文。
由于美观是历史建筑的主要支柱,Darius 希望柱子的高度不断上升。为了避免工人付出过多的努力,他要求你计划一系列最多 $$$n$$$ 的移动,根据铭文的数量以非递减的顺序排列柱子。不需要最小化移动次数。
输入
第一行包含一个整数 $$$t$$$ — 测试用例的数量。 ($$$1 \leq t \leq 3000$$$)
每个测试用例的第一行包含一个整数 $$$n$$$ — 石柱的数量。 ($$$1 \leq n \leq 2 \cdot 10^5$$$)
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,其中 $$$a_i \in \{0,1,2\}$$$ 表示第 $$$i$$$ 列中的初始铭文数量。保证至少有一列恰好有 $$$1$$$ 铭文。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 $$$k$$$ — 用于对列进行排序的移动次数。 ($$$0 \leq k \leq n$$$)
然后,输出 $$$k$$$ 行,每行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),表示第 $$$i$$$ 移动中涉及的列的索引。在每次移动过程中,它必须保持 $$$|a_{u_i} - a_{v_i}| = 1$$$,一个铭文从具有更多铭文的列转移到另一列。
可以证明,在给定的约束条件下,始终存在有效的解。
示例
输入 #1
3 4 0 2 0 1 3 1 2 0 6 0 1 1 2 2 2
输出 #1
2 2 4 2 3 2 3 1 2 3 0
注意
第一个测试用例中的列状态:
- 初始:$$$0, 2, 0, 1$$$
- 第一次移动后:$$$0, 1, 0, 2$$$
- 第二次移动后:$$$0, 0, 1, 2$$$
第二个测试用例中的列状态:
- 初始:$$$1, 2, 0$$$
- 第一步之后:$$$0, 2, 1$$$
- 第二次移动后:$$$0, 1, 2$$$
在第三个测试用例中,列高已按升序排序。