Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Формат входных данных
Во входном файле содержится единственное число A (1 ≤ A ≤ 1000000000 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы кого-нибудь “завалить”).
Формат выходных данных
В выходной файл выведите единственное число N.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8 |
4 |
| 2 |
13 |
13 |