题目描述

给你一个整数 $n$ ，返回和为 $n$ 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，$1、4、9$ 和 $16$ 都是完全平方数，而 $3$ 和 $11$ 不是。

输入格式

一行一个整数$n(1 <= n <= 10^4)$

输出格式

一行一个整数,和为 $n$ 的完全平方数的最少数量。

样例1

12

3

样例2

13

2

提示说明

样例 1：

输入：n = 12

输出：3

解释：12 = 4 + 4 + 4

样例 2：

输入：n = 13

输出：2

解释：13 = 4 + 9

30%数据 $1<=n<=10^2$

60%数据 $1<=n<=10^3$

100%数据 $1<=n<=10^4$