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. \InputFile One positive integer $n\:(n \le 10^9)$. \OutputFile 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.