一个名为 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$$$ 的所有除数可以按某种顺序放置,以便不存在互质的两个相邻数字。