You are given a positive integer n. Output its prime factorization.

If n = a₁^b₁ a₂^b₂ ... a_k^b_k (b_i > 0), where a_k are prime numbers, the output of your program should look as follows: a₁*...*a₁*a₂*...*a₂*...*a_k*...*a_k, where the factors are ordered in non-decreasing order, and each factor a_i is printed b_i times.

The only line of input contains an integer n (2 ≤ n ≤ 10000).

Output the prime factorization of n, as described above.