← 返回题目列表

Codeforces · 1762/B

B. 使阵列良好

中文机器翻译题面 查看原题

如果对于所有对 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i,j \leq m$$$),$$$\max(b_i,b_j)$$$ 可以被 $$$\min(b_i,b_j)$$$ 整除,则 $$$m$$$ 正整数的数组 $$$b$$$ 是好的。

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。您可以执行以下操作:

- 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 和整数 $$$x$$$ ($$$0 \leq x \leq a_i$$$) 并将 $$$x$$$ 添加到 $$$a_i$$$,换句话说,$$$a_i := a_i+x$$$。
- 执行此操作后,应满足 $$$a_i \leq 10^{18}$$$ 。

你必须构造一个最多 $$$n$$$ 操作的序列,这将使 $$$a$$$ 变得更好。可以证明,在问题的约束下,这样的操作序列总是存在的。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 表示数组 $$$a$$$。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试,输出一个整数 $$$p$$$ ($$$0 \leq p \leq n$$$) — 表示解决方案中的操作数。

在下面的每一行 $$$p$$$ 中,输出两个空格分隔的整数 — $$$i$$$ 和 $$$x$$$。

您不需要最小化操作次数。可以证明,解总是存在的。

示例

输入 #1

4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17

输出 #1

4
1 2
1 1
2 2
3 0
0
5
1 3
1 4
2 1
5 4
3 7
3
1 29
2 5
3 3

注意

在第一个测试用例中,数组 $$$a$$$ 在操作后变为 $$$[5,5,5,5]$$$。很容易看出 $$$[5,5,5,5]$$$ 很好。

在第二个测试用例中,数组 $$$a$$$ 已经很好了。

在第三个测试用例中,执行操作后,数组 $$$a$$$ 变为 $$$[10,5,350,5,10]$$$,这很好。

在第四个测试用例中,执行操作后,数组 $$$a$$$ 变为 $$$[60,10,20]$$$,这很好。