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