Short cube
Write a program that, given a natural number k, determines the smallest natural number whose cube is a multiple of k.
Input
A single natural number k.
Output
Print a single natural number — the smallest positive integer whose cube (third power) is divisible by k without a remainder.
Example
For example, neither 1^3=1, nor 2^3=8, nor 3^3=27, nor 4^3=64, nor 5^3=125 are divisible by 12 without a remainder, but 6^3=216 is divisible. Thus, 6^3 is the smallest natural cube that is a multiple of 12.
Evaluation
20% of the points are for tests where
2 ≤ k ≤ 100;20% of the points are for
10^5 < k < 10^6;20% of the points are for
10^7 < k < 10^8;20% of the points are for
10^10 < k < 10^12;20% of the points are for
10^15 < k < 10^18.
You need to write a single program that handles all these cases efficiently. The breakdown of constraints is provided to indicate how points are distributed based on the efficiency of your solution.