CF1419E Decryption

有一个名为 Cypher 的特工正在解密一条包含一个复合数 $n$ 的消息。$n$ 的所有大于 $1$ 的约数被放置在一个圆圈中。Cypher 可以选择这些数字在圆圈中的初始排列顺序。 在每一步操作中，Cypher 可以选择圆圈中相邻的两个数字，并在它们之间插入它们的最小公倍数。他可以进行任意多次这样的操作。 当圆圈中每一对相邻的数字都不是互质时，消息就被解密。注意，对于本题的约束条件，总是可以解密消息。 请你求出 Cypher 至少需要多少次操作才能解密消息，并给出一种初始排列顺序。

第一行包含一个整数 $t$ $(1 \le t \le 100)$，表示测试用例的数量。接下来的 $t$ 行描述每个测试用例。 每个测试用例包含一行，一个复合数 $n$ $(4 \le n \le 10^9)$，即消息中的数字。 保证所有测试用例中 $n$ 的约数总数之和不超过 $2 \cdot 10^5$。

对于每个测试用例，第一行输出大于 $1$ 的约数的初始排列顺序（以空格分隔），按圆圈顺序排列。第二行输出解密消息所需的最小操作次数。 如果存在多种排列顺序都能得到正确答案，输出任意一种即可。

在第一个测试用例中，$6$ 有三个大于 $1$ 的约数：$2, 3, 6$。无论初始顺序如何，$2$ 和 $3$ 都会相邻，因此需要在它们之间插入它们的最小公倍数。此后，圆圈变为 $2, 6, 3, 6$，每一对相邻数字都不是互质。 在第二个测试用例中，$4$ 有两个大于 $1$ 的约数：$2, 4$，它们不是互质，因此任意初始顺序都可以，不需要插入最小公倍数。 在第三个测试用例中，$30$ 的所有大于 $1$ 的约数可以按某种顺序排列，使得没有两对相邻数字是互质的。 由 ChatGPT 4.1 翻译