题目描述

给你一个整数 $a(1 \le a \le 10^6)$，要求将 $a$ 表示成 $n$ 个正整数的立方之和的形式，且 $n$ 最小。

比如：

• $36=1^3+2^3+3^3$，所以当 $a=36$ 时，对应的最小的 $n$ 为 $3$；
• $152=3^3+5^3$，所以当 $a=152$ 时，对应的最小的 $n$ 为 $2$。

输入格式

一个整数 $a(1 \le a \le 10^6)$。

输出格式

一个整数 $n$，表示 $a$ 最少能表示成多少个正整数的立方和。

样例

36

3

152

2

数据范围

• 对于 $20\%$ 的数据，$a \le 100$；
• 对于 $40\%$ 的数据，$a \le 1000$；
• 对于 $60\%$ 的数据，$a \le 10000$；
• 对于 $80\%$ 的数据，$a \le 10^5$；
• 对于 $100\%$ 的数据，$1 \le a \le 10^6$。