给定一个正整数数组 $$$a_1, a_2, \ldots, a_n$$$。
您可以多次(可能为零)执行此操作:
- 选择两个索引 $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$)。
- 分配 $$$a_i := \lceil \frac{a_i}{a_j} \rceil$$$。这里 $$$\lceil x \rceil$$$ 表示 $$$x$$$ 四舍五入到最小整数 $$$\geq x$$$。
是否可以通过某些操作序列(可能为空)使所有数组元素相等?如果是,请打印最多 $$$30n$$$ 操作中执行此操作的任何方法。
可以证明,在问题约束下,如果存在某种方法使所有元素相等,则存在最多$$$30n$$$操作的方法。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$)。
每个测试用例描述的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,打印一个整数 $$$q$$$ ($$$-1 \leq q \leq 30n$$$)。如果$$$q=-1$$$则无解,否则$$$q$$$等于运算次数。
如果 $$$q \geq 0$$$,则在接下来的 $$$q$$$ 行中打印两个整数 $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) — 操作描述。
如果有多个解决方案,您可以打印任意一个。
示例
输入 #1
10 1 100 3 1 1 1 2 2 1 2 5 5 3 4 3 2 4 3 3 4 4 2 2 100 5 5 3 6 7 8 6 3 3 80 3 8 3 4 19 40 19 55
输出 #1
0 0 -1 0 2 1 3 2 1 4 3 1 4 2 1 3 2 4 6 2 1 2 1 2 1 2 1 2 1 2 1 8 5 2 4 2 3 2 1 3 1 3 2 1 4 1 5 1 4 5 1 3 1 3 1 3 1 9 4 2 2 1 1 2 1 2 3 2 3 2 1 4 2 4 3 4
注意
在第一个、第二个、第四个测试用例中,所有数字都相等,因此可以什么都不做。
在第三个测试用例中,不可能使所有数字相等。
在第五个测试用例中:$$$[\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2]$$$。
在第六个测试用例中: $$$[\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \ 到 [2, 2, 2, 2]$$$。
这里红色数字是 $$$i$$$ 索引(将被分配),蓝色数字是 $$$j$$$ 索引。