Степінь

Для того щоб перевірити, як її учні вміють рахувати, Марія Іванівна кожного року задає їм додому одну і ту ж задачу – для заданого натурального A знайти мінімальне натуральне N таке, що N у степені N (N, помножене на себе N разів) ділиться на A. Від року до року і від учня до учня змінюється лише число A.

Ви вирішили допомогти майбутнім поколінням. Для цього вам необхідно написати програму, яка розв'язує цю задачу.

Вхідні дані

У вхідному файлі міститься єдине число A (1 ≤ A ≤ 1000000000 – про всякий випадок; а раптом Марія Іванівна задасть велике число, щоб "завалити" кого-небудь…).

Вихідні дані

У вихідний файл вивести єдине число N.

Приклади