C. Divisor Circle
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Consider all divisors of some integer $$$n$$$. Choose some of these divisors, then arrange them in a circle so that the ratio of any two adjacent numbers is a prime number.

Find the maximum number of divisors of $$$n$$$ you can choose, and find the appropriate arrangement.

Input

The first line of input contains the integer $$$n$$$ ($$$2 \le n \le 10^9$$$).

Output

In the first line, print a single integer $$$k$$$ — the maximum number of divisors of $$$n$$$ you can choose.

In the second line, print $$$k$$$ integers — different divisors of $$$n$$$ in the order they appear on the circle. Any two adjacent and the first and last numbers in this list must differ by multiplication by some prime number.

Scoring
SubtaskScoreConstraints
$$$1$$$$$$10$$$$$$n \le 10$$$
$$$2$$$$$$15$$$$$$n \le 50$$$
$$$3$$$$$$20$$$$$$n \le 150$$$
$$$4$$$$$$20$$$$$$n = 10^m$$$ for integer $$$m \ge 0$$$
$$$5$$$$$$15$$$$$$n = 2^x \cdot 3^y \cdot 5^z$$$ for integers $$$x, y, z \ge 0$$$
$$$6$$$$$$10$$$$$$n$$$ is not a square of an integer
$$$7$$$$$$10$$$No additional constraints
Example
Input
10
Output
4
1 2 10 5