Factor a positive integer into prime factors, including repeated factors.

Input

One line containing \(n\).

The input satisfies:

• \(2 \le n \le 10^12\)

Output

Print the prime factors in non-decreasing order, separated by single spaces.

Example

Input

772608034109

Output

772608034109