codeforces#P1419E. Decryption

    ID: 31489 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>constructive algorithmsimplementationmathnumber theory*2100

Decryption

Description

An agent called Cypher is decrypting a message, that contains a composite number nn. All divisors of nn, which are greater than 11, 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.

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

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

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

For each test case in the first line output the initial order of divisors, which are greater than 11, 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.

Input

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

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

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

Output

For each test case in the first line output the initial order of divisors, which are greater than 11, 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.

Samples

输入数据 1

3
6
4
30

输出数据 1

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

Note

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

In the second test case 44 has two divisors greater than 11: 2,42, 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 3030 greater than 11 can be placed in some order so that there are no two adjacent numbers that are coprime.