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.
One positive integer n(n≤109).
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.