给定一个正整数n,请找出最少个数的完全平方数,使得这些完全平方数的和等于n。 完全平方指用一个整数乘以自己例如1*1,2*2,3*3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。例如:1,4,9,和16都是完全平方数,但是2,3,5,8,11等等不是 数据范围:
输入描述:
仅一行,输入一个正整数 n 


输出描述:
按题目要求输出完全平方数之和为n的最少个数
示例1

输入

5

输出

2

说明

1+4=5
示例2

输入

8

输出

2

说明

4+4=8
示例3

输入

9

输出

1

说明

3^2 = 9 \
加载中...