The Lesson of Mathematics#572
At the beginning of each lesson, the mathematics teacher Olga Petrivna writes a positive integer on the board. During the lesson, the students try to find as many prime factors of this number as possible. At the end of the lesson, the generous Olga Petrivna rewards all students who found the maximum number of prime factors with a candy.
Vasya, a student who loves sweets, asks for your help to receive a candy from Olga Petrivna. For the given number , output all its prime factors and the powers with which they occur in the number.
A single positive integer , where n \le 10^9.
Output all the prime factors of the number in ascending order. For each factor, specify the power with which it occurs in , if the power is greater than one. The output format must match the example.
Example 1