The Lesson of mathematics

At the beginning of each lesson the teacher of mathematics Guzel Zakievna writes on the blackboard one positive integer n. While the lesson the students are trying to find as much as possible prime factors of that number. At the end of the lesson generous Guzel Zakievna gives sweets to all those who have found the maximum number of prime divisors. Vassya the pupil loves sweets and asks you to help him to have some from Guzel Zakievny today. For the given number of n, print all its prime factors and degrees in which they occur in the given number.


One positive integer n (n109).


Print all the prime factors of n in ascending order and for each divisor specify its degree with which it occurs in n, if this degree is greater than one. The output format must match the example.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Source SCS 2009