试题名称：小杨和整数拆分 时间限制：20.0 s 内存限制：512.0 MB
题面描述 小杨有一个正整数 $n$，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为 $n$ 的完全平方数的最少数量。
输入格式 第一行包含一个正整数 $n$，含义如题面所示。
输出格式 输出一个整数，代表总和为 $n$ 的完全平方数的最少数量。
样例1
18
2$18 = 9 + 9 = 16 + 1 + 1$，其中最少需要 2 个完全平方数。
| 子任务编号 | 数据点占比 | $n$ |
|---|---|---|
| 1 | 20% | $\le 20$ |
| 2 | 40% | $\le 1000$ |
| 3 | 40% | $\le 10^5$ |
对于全部数据，保证有 $1 \le n \le 10^5$。