测试数据来自 nnu_contest/1272

数字分解

时间限制:1s

空间限制:64MB

题目描述

分解整数$n$，将其分成$m$个四次方数的和，问$m$至少是多少？

输入格式

一个正整数$n$

输出格式

一个整数，表示分成四次方数的数量$m$的最小值。

样例输入1

18

样例输出1

3

样例1解释

$18=2^4+1^4+1^4$

样例输入2

706

样例输出2

2

样例2解释

$706=5^4+3^4$

样例输入3

4322

样例输出3

3

样例3解释

$4322=7^4+6^4+5^4$

数据范围及限制

对于$80\%$的数据，$1\le n\le 1000$
提示：对于$n$较小的情况，可以通过枚举解决。

对于$100\%$的数据，$1\le n \le 100000$