题目描述

将一个整数 n 分解为若干个四次方数的和，求四次方数的最小个数。

例如对 n=17，17=$2^{4}$+$1^{4}$，最小个数为 2。

输入格式

一行，一个整数 n。

输出格式

一行，一个整数，为最小个数。

输入样例 #1

17

输出样例 #1

2

输入样例 #2

685

输出样例 #2

15

输入样例 #3

80757

输出样例 #3

7

数据范围与约定

对于 30% 的数据，0≤n≤5000；对于 100% 的数据，0≤n≤100,000。