Background

With your help, v 神 (v shen) finally found the most suitable university for a classmate, and now it is time to inform them. The classmate in charge of the contact network in the class is dm, so v 神 went to find dm. However, dm was busy studying an interesting math problem. To invite dm to help, v 神 asked you to solve this problem.

Problem 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