题目内容

如果一个整数可以表示为某个整数与自身相乘的积，就称它为完全平方数。例如，$1 = 1 \times 1$、$4 = 2 \times 2$、$9 = 3 \times 3$、$16 = 4 \times 4$，这些数都是完全平方数；而 $5$ 和 $12$ 不是。

给定一个整数 $n$，请计算至少需要多少个完全平方数相加才能得到 $n$。

约束条件

整数 $n$ 满足 $1 \le n \le 10^4$。

输入描述

输入包含一个参数：一个整数 $n$，表示需要用完全平方数凑出的目标整数。

输出描述

返回一个整数，表示凑出 $n$ 所需的最少完全平方数个数。

样例1

输入

1

输出

1

说明

1 本身是完全平方数，因为 $1 = 1^2$，所以最少需要 1 个完全平方数。

样例2

输入

41

输出

2

说明

$41 = 25 + 16 = 5^2 + 4^2$，最少需要 2 个完全平方数。

样例3

输入

43

输出

3

说明

一种最优拆分是 $43 = 25 + 9 + 9 = 5^2 + 3^2 + 3^2$，因此最少需要 3 个完全平方数。

样例4

输入

10000

输出

1

说明

10000 可以写成 $100^2$，本身是完全平方数，所以最少需要 1 个完全平方数。