Decomposition into a sum of cubes

One positive integer $n$ is given. Represent it as the sum of the minimum number of positive cubes. Print this minimum number.

Input

One positive integer $n(1\le n\le 10^6)$.

Output

Print one integer - the minimum number of positive cubes whose sum equals $n$.

Examples