The Jewel Thief

Interview

Time limit2sMemory limit512 MB

Summary

Factor k into the largest possible count of integers greater than 1 whose product is k, and list them in ascending order.

Level: Medium6 of 10
Topics: Number theory, Greedy
Solved: No attempts yet

Problem

Hyobin the thief plans to break into a jewelry store. The store's security system cannot be switched off, and while it runs, jewels taken together stick to each other: their combined weight becomes the product of the individual weights.

Hyobin gives up on the security system and accepts the multiplied weight. He can carry a weight of $k$ in one trip and wants to walk out with exactly that weight, so the weights of the jewels he takes must multiply to exactly $k$ .

The store holds plenty of jewels of every integer weight greater than 1, so he may take several jewels of the same weight.

Find the largest number of jewels whose weights multiply to exactly $k$ , and find those weights. When the number of jewels is largest, the collection of weights is unique.

Input

The first line contains the weight $k$ that Hyobin can carry in one trip. ( $2 \le k \le 10^{12}$ )

Output

On the first line, print the largest number of jewels Hyobin can take. On the second line, print the weights of those jewels in ascending order, separated by single spaces.

Examples2

Example 1
Input
```
15
```
Expected output
```
2
3 5
```
Example 2
Input
```
2
```
Expected output
```
1
2
```