Short cube — Eolymp

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.

Examples

Example 1

Loading

Note

For example, neither $1^{3} = 1$ 1^3 = 1, nor $2^{3} = 8$ 2^3 = 8, nor $3^{3} = 27$ 3^3 = 27, nor $4^{3} = 64$ 4^3 = 64, nor $5^{3} = 125$ 5^3 = 125 are divisible by $12$ without a remainder, but $6^{3} = 216$ 6^3 = 216 is divisible. Thus, $6^{3}$ 6^3 is the smallest natural cube that is a multiple of $12$ .

Scoring

$20%$ of the points are for tests where $2 \leq k \leq 100$ 2 \leq k \leq 100;
$20%$ of the points for $1 0^{5} < k < 1 0^{6}$ 10^5 < k < 10^6;
$20%$ of the points for $1 0^{7} < k < 1 0^{8}$ 10^7 < k < 10^8;
$20%$ of the points for $1 0^{10} < k < 1 0^{12}$ 10^{10} < k < 10^{12};
$20%$ of the points for $1 0^{15} < k < 1 0^{18}$ 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.