The Lesson of mathematics

At the beginning of each lesson, the math teacher, Guzel Zakievna, writes on the board one positive integer $n$. While the lesson is ongoing, the students try to find as many prime divisors of this number as possible. At the end of the lesson, generous Guzel Zakievna gives a candy to all those who have found the maximum number of prime divisors. Vasya, a student, loves sweets and asks you to provide him with a candy from Guzel Zakievna today. Given the number $n$, print all its prime divisors and the powers to which they appear in the given number.

Input

One positive integer $n(n\le 10^9)$.

Output

Print all prime divisors of the number $n$ in ascending order and indicate the exponent for each divisor if its exponent is greater than one. The output format should match the example.

Examples