Урок математики

На початку кожного уроку вчителька математики Гузель Закіївна пише на дошці натуральне число $n$. Доки йде урок школярі намагаються знайти якомога більше простих дільників цього числа. В кінці уроку щедра Гузель Закіївна роздає цукерку всім тим, хто знайшов максимальну кількусть простих дільників. Школяр Вася обожнює солодке і просить вас забезпечити йому цукерку від Гузель Закіївни сьогодні. За заданим числом $n$ потрібно вивести всі його прості дільники в степені, у якому вони зустрічаються у заданому числі.

Вхідні дані

Єдине натуральне число $n(n\le 10^9)$.

Вихідні дані

Виведіть усі прості дільники числа у порядку зростання і вкажіть для кожного дільника степінь, у якій він зустрічається в числі $n$, якщо його степінь більше одиниці. Формат виведення повинен відповідати прикладу.

Приклади