В начале каждого урока учительница математики Гузель Закиевна пишет на доске натуральное число $n$. Пока идет урок школьники пытаются найти как можно больше простых делителей этого числа. В конце урока щедрая Гузель Закиевна выдает конфетку всем тем, кто нашел максимальное количество простых делителей. Школьник Вася обожает сладкое и просит вас обеспечить ему конфетку от Гузель Закиевны сегодня. По заданному числу $n$ вывести все его простые делители в степени, в которой они встречаются в данном числе. \InputFile Одно натуральное число $n\:(n \le 10^9)$. \OutputFile Выведите все простые делители числа в порядке возрастания и укажите для каждого делителя степень, в которой он встречается в числе $n$, если его степень больше единицы. Формат вывода должен соответствовать примеру.