Nastia 收到了一组 $$$n$$$ 正整数作为礼物。
她称这样的数组 $$$a$$$ 很好,对于所有 $$$i$$$ ($$$2 \le i \le n$$$) 都发生 $$$gcd(a_{i - 1}, a_{i}) = 1$$$,其中 $$$gcd(u, v)$$$ 表示整数 $$$u$$$ 的最大公约数 (GCD), $$$v$$$。
可以执行以下操作:选择两个不同的索引 $$$i, j$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$) 和两个整数 $$$x, y$$$ ($$$1 \le x, y \le 2 \cdot 10^9$$$) 使得 $$$\min{(a_i, a_j)} = \min{(x, y)}$$$。然后将 $$$a_i$$$ 更改为 $$$x$$$,并将 $$$a_j$$$ 更改为 $$$y$$$。
女孩要求你最多使用 $$$n$$$ 操作来使数组变得良好。
可以证明这总是可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_{n}$$$ ($$$1 \le a_i \le 10^9$$$) - Nastia 作为礼物收到的数组。
保证一次测试中 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个 $$$t$$$ 测试用例,打印一个整数 $$$k$$$ ($$$0 \le k \le n$$$) — 操作数。您不需要最小化这个数字。
在接下来的 $$$k$$$ 行中,打印 $$$4$$$ 整数 $$$i$$$, $$$j$$$, $$$x$$$, $$$y$$$ ($$$1 \le i \neq j \le n$$$, $$$1 \le x, y \le 2 \cdot 10^9$$$) 以便$$$\min{(a_i, a_j)} = \min{(x, y)}$$$ - 通过这种方式,您可以将 $$$a_i$$$ 替换为 $$$x$$$,将 $$$a_j$$$ 替换为 $$$y$$$。
如果有多个答案,请打印其中一个。
示例
输入 #1
2 5 9 6 3 11 15 3 7 5 13
输出 #1
2 1 5 11 9 2 5 7 6 0
注意
考虑第一个测试用例。
最初 $$$a = [9, 6, 3, 11, 15]$$$。
在第一个操作中,将 $$$a_1$$$ 替换为 $$$11$$$,将 $$$a_5$$$ 替换为 $$$9$$$。这是有效的,因为 $$$\min{(a_1, a_5)} = \min{(11, 9)} = 9$$$。
之后 $$$a = [11, 6, 3, 11, 9]$$$。
在第二个操作中,将 $$$a_2$$$ 替换为 $$$7$$$,将 $$$a_5$$$ 替换为 $$$6$$$。这是有效的,因为 $$$\min{(a_2, a_5)} = \min{(7, 6)} = 6$$$。
之后 $$$a = [11, 7, 3, 11, 6]$$$ — 一个很好的数组。
在第二个测试用例中,初始数组已经很好。