You are given an integer n. Output its prime factorization.

If n = a₁^b₁a₂^b₂ ... a_k^b_k, where a_k are prime numbers, the output of your program should look as follows: a₁ a₁ ... a₁ a₂ a₂ ... a₂ ... a_k a_k ... a_k, where 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 ≤ 250).

Output the prime factorization of n, as described above.