CF1521B Nastia and a Good Array

Nastia 收到了一份包含 $n$ 个正整数的数组作为礼物。 她称一个数组 $a$ 是“好”的，当且仅当对于所有 $i$（$2 \le i \le n$），都有 $gcd(a_{i-1}, a_i) = 1$，其中 $gcd(u, v)$ 表示整数 $u$ 和 $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$。 Nastia 希望你用不超过 $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$。

对于每个测试用例，输出一个整数 $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$），表示你将 $a_i$ 变为 $x$，$a_j$ 变为 $y$，并且满足 $\min(a_i, a_j) = \min(x, y)$。 如果有多组答案，输出任意一组均可。

考虑第一个测试用例。 初始时 $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]$，这是一个“好”的数组。 第二个测试用例中，初始数组已经是“好”的。 由 ChatGPT 4.1 翻译