四次方数

题目描述

任何一个整数都可以分解出n个四次方数和的形式，例如：81=3^4,81=2^4+2^4+2^4+2^4+2^4+1^4, 那么，81既可以分解为1个四次方数，也可以分解为5个四次方数。但要求只输出满足要求的最小值n，在本例中显然n=1。

输入格式

一行，一个整数m。

输出格式

一行，一个整数n。

样例 #1

样例输入 #1

81

样例输出 #1

1

提示

数据范围：对于30%的数据，m<=5000;对于100%的数据，m<=100,000