CF1419E.Decryption

An agent called Cypher is decrypting a message, that contains a composite number $n$. All divisors of $n$, which are greater than $1$, are placed in a circle. Cypher can choose the initial order of numbers in the circle.

In one move Cypher can choose two adjacent numbers in a circle and insert their least common multiple between them. He can do that move as many times as needed.

A message is decrypted, if every two adjacent numbers are not coprime. Note that for such constraints it's always possible to decrypt the message.

Find the minimal number of moves that Cypher should do to decrypt the message, and show the initial order of numbers in the circle for that.

一名名为“密码破解者”（Cypher）的代理正在解密一条包含一个合数 $n$ 的消息。将 $n$ 的所有大于 $1$ 的正因数按某种顺序排成一个环形。Cypher 可以自行选择这些数在环中的初始排列顺序。

在一次操作中，Cypher 可以选择环中两个相邻的数，并将它们的最小公倍数插入到这两个数之间（即在环中新增一个数）。该操作可执行任意多次。

当环中每一对相邻数均不互质（即其最大公约数大于 $1$）时，消息即被成功解密。注意：在本题约束下，总存在一种方式能成功解密该消息。

请找出 Cypher 为解密该消息所需的最少操作次数，并给出达到该最少次数所对应的环的初始排列顺序。

The first line contains an integer $t$ $(1 \le t \le 100)$ — the number of test cases. Next $t$ lines describe each test case.

In a single line of each test case description, there is a single composite number $n$ $(4 \le n \le 10^9)$ — the number from the message.

It's guaranteed that the total number of divisors of $n$ for all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 100$）——测试用例的数量。接下来的 $t$ 行分别描述每个测试用例。

每个测试用例的描述占一行，其中包含一个合数 $n$（$4 \le n \le 10^9$）——即消息中的该数。

保证所有测试用例中 $n$ 的约数总数不超过 $2 \cdot 10^5$。

For each test case in the first line output the initial order of divisors, which are greater than $1$, in the circle. In the second line output, the minimal number of moves needed to decrypt the message.

If there are different possible orders with a correct answer, print any of them.

对于每个测试用例，第一行输出圆圈中大于 $1$ 的约数的初始顺序；第二行输出解密该消息所需的最少移动次数。

如果存在多种可能的正确顺序，请输出其中任意一种。

In the first test case $6$ has three divisors, which are greater than $1$: $2, 3, 6$. Regardless of the initial order, numbers $2$ and $3$ are adjacent, so it's needed to place their least common multiple between them. After that the circle becomes $2, 6, 3, 6$, and every two adjacent numbers are not coprime.

In the second test case $4$ has two divisors greater than $1$: $2, 4$, and they are not coprime, so any initial order is correct, and it's not needed to place any least common multiples.

In the third test case all divisors of $30$ greater than $1$ can be placed in some order so that there are no two adjacent numbers that are coprime.

在第一个测试用例中，$6$ 有三个大于 $1$ 的约数：$2, 3, 6$。无论初始顺序如何，数字 $2$ 和 $3$ 总是相邻的，因此需要在其间插入它们的最小公倍数。操作之后，圆圈变为 $2, 6, 3, 6$，此时任意两个相邻数字均不互质。

在第二个测试用例中，$4$ 有两个大于 $1$ 的约数：$2, 4$，且它们不互质，因此任意初始顺序均合法，无需插入任何最小公倍数。

在第三个测试用例中，$30$ 的所有大于 $1$ 的约数均可按某种顺序排列，使得任意两个相邻数字均不互质。