Description

Decompose an integer $m$ into a sum of $n$ fourth powers, with $n$ being as small as possible. For example, when $m=706$, since $706=5^4+3^4$, we have $n=2$. It can be proven that in this case $n$ is minimal.

Input Format

One line, an integer $m$.

Output Format

One line, an integer $n$.

706

2

Hint

Constraints

• For $30\%$ of the testdata, $m \le 5000$.
• For $100\%$ of the testdata, $m \le 100{,}000$.

Translated by ChatGPT 5