Factorization

Find the factorization of the given numbers.

Input

Each line contains one positive integer $n(n\le 10^7)$.

Output

For each input value $n$ print its factorization as shown in the sample input.

Examples