M. Степень

Для заданного натурального $A$ найдите наименьшее натуральное $N$ такое, что $N^N$ (то есть $N$, умноженное само на себя $N$ раз) делится на $A$.

Одна строка содержит число $A$ ($1 \le A \le 10^9$).

Одно число — наименьшее подходящее $N$.