给定一个数组 $$$a$$$,其中包含 $$$n$$$ 非负整数。您可以对其应用以下操作。
- 选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$)。
- 如果 $$$a_l + a_r$$$ 是奇数,则执行 $$$a_r := a_l$$$。如果 $$$a_l + a_r$$$ 是偶数,则执行 $$$a_l := a_r$$$。
找到最多 $$$n$$$ 操作的任何序列,使 $$$a$$$ 非递减。可以证明它总是可能的。请注意,您不必最小化操作数量。
数组 $$$a_1, a_2, \ldots, a_n$$$ 是非递减的当且仅当 $$$a_1 \le a_2 \le \ldots \le a_n$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
每个测试用例由两行组成。每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) - 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组本身。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在第一行打印一个整数 $$$m$$$ ($$$0 \le m \le n$$$),即操作数。
然后打印 $$$m$$$ 行。每行必须包含两个整数 $$$l_i、r_i$$$,它们是您在第 $$$i$$$ 操作中选择的索引 ($$$1 \le l_i < r_i \le n$$$)。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
3 2 7 8 5 1 1000000000 3 0 5 1 0
输出 #1
0 2 3 4 1 2 0
注意
在第二个测试用例中,$$$a$$$ 变化如下:
- 选择索引 $$$3$$$ 和 $$$4$$$。 $$$a_3 + a_4 = 3$$$ 是奇数,$$$a_4 := a_3$$$ 也是奇数。 $$$a = [1, 1000000000, 3, 3, 5]$$$ 现在。
- 选择索引 $$$1$$$ 和 $$$2$$$。 $$$a_1 + a_2 = 1000000001$$$ 是奇数,$$$a_2 := a_1$$$ 也是奇数。现在 $$$a = [1, 1, 3, 3, 5]$$$,并且它是非递减的。
在第一个和第三个测试用例中,$$$a$$$ 已经是非递减的。