题目描述

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

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

输入格式

一行一个整数 $n$。

输出格式

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

样例

样例 1：

输入：

12

输出：

3

解释：12 = 4 + 4 + 4

样例 2：

输入：

13

输出：

2

解释：13 = 4 + 9

数据规模：

• $1 \le n \le 10^4$