Prime factorization

3000ms

262144K

Description:

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.

Input:

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

Output:

Output the prime factorization of n, as described above.

Sample Input:

Sample Output:

5*7*7

Sample Input:

Sample Output:

Informação

Provedor Codeforces

Código CF162C