300847: CF162C. Prime factorization

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Prime factorizationtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

If n = a1b1 a2b2 ... akbk (bi > 0), where ak are prime numbers, the output of your program should look as follows: a1*...*a1*a2*...*a2*...*ak*...*ak, where the factors are ordered in non-decreasing order, and each factor ai is printed bi times.

Input

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

Output

Output the prime factorization of n, as described above.

ExamplesInput
245
Output
5*7*7
Input
19
Output
19

Input

加入题单

上一题 下一题 算法标签: