← 返回题目列表

Codeforces · 1419/E

E. 解密

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

一个名为 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$$$ 的除数的初始顺序。在第二行输出中,解密消息所需的最少移动次数。

如果有不同的可能顺序且有正确答案,请打印其中任何一个。

示例

输入 #1

3
6
4
30

输出 #1

2 3 6 
1
2 4 
0
2 30 6 3 15 5 10 
0

注意

在第一个测试用例中,$$$6$$$ 有三个大于 $$$1$$$ 的除数:$$$2, 3, 6$$$。无论初始顺序如何,数字 $$$2$$$ 和 $$$3$$$ 都是相邻的,因此需要将它们的最小公倍数放在它们之间。之后圆就变成$$$2, 6, 3, 6$$$,并且每两个相邻的数字互质。

在第二个测试用例中,$$$4$$$ 有两个大于 $$$1$$$ 的约数:$$$2、4$$$,并且它们不是互质的,因此任何初始顺序都是正确的,并且不需要放置任何最小公倍数。

在第三个测试用例中,$$$30$$$ 大于 $$$1$$$ 的所有除数可以按某种顺序放置,以便不存在互质的两个相邻数字。