题目描述

将一个整数 $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$。