Краткий куб

Напишите программу, которая для заданного натурального числа k найдет наименьшее натуральное число, куб которого делится на k.

Входные данные

Одно натуральное число k.

Выходные данные

Выведите одно число — минимальное натуральное число, куб которого делится на k без остатка.

Примеры

Примечание

Ни 1^3=1, ни 2^3=8, ни 3^3=27, ни 4^3=64, ни 5^3=125 не делятся на 12 без остатка, а 6^3=216 делится. Таким образом, 6^3 является наименьшим натуральным кубом, кратным 12.

Оценивание

20% баллов приходится на тесты, где 2 ≤ k ≤ 100;

20% баллов — на 10^5 < k < 10^6;

20% баллов — на 10^7 < k < 10^8;

20% баллов — на 10^10 < k < 10^12;

20% баллов — на 10^15 < k < 10^18.

Необходимо написать одну программу, а не несколько для разных случаев; цель перечисления различных блоков ограничений — показать, сколько баллов можно получить, если задача решена правильно, но неэффективно.