测试数据来自 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\)