题目描述

将一个整数 \(m\) 分解为 \(n\) 个四次方数的和的形式，要求 \(n\) 最小。例如，\(m=706,706=5^4+3^4\),则 \(n=2\)。

格式

输入格式

一行，一个整数 \(m\)。

输出格式

一行，一个整数 \(n\)。

样例1

样例输入1

706

样例输出1

2

限制

对于 \(30\%\) 的数据，\(m<=5000\);

对于 \(100\%\) 的数据，\(m<=100,000\)。