1297 - 完全平方数

给你一个整数 n ,得到 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

输入

一个整数n

输出

和为 n 的完全平方数的最少数量

样例

输入

12

输出

3

输入

13

输出

2

提示

1 <= n <= 10^4

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题