P83073

完全平方数

题目描述

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

输入

一个正整数n。

输出

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

样例

样例 1

输入

13

输出

2

提示

样例说明：13=4+9。

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

来源

动规专题