如果对于所有对 $$$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]$$$,这很好。