3073 - 完全平方数

给定一个正整数n,问最少可以将n分成几个完全平方数之和。完全平方数是指1,4,9,...等。

输入

一个正整数n。

输出

一个正整数m,表示n最少可以分成m个完全平方数

样例

输入

13

输出

2

提示

样例说明:13=4+9。

对于所有数据,n\le 10^{6}.

来源

动规专题

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