小杨和整数拆分

题面描述

小杨有一个正整数 $n$，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。

小杨请你编写程序计算出总和为 $n$ 的完全平方数的最少数量。

输入格式

第一行包含一个正整数 $n$，含义如题面所示。

输出格式

输出一个整数，代表总和为 $n$ 的完全平方数的最少数量。

样例1

118

12

$18=9+9=16+1+1$，其中最少需要 $2$ 个完全平方数。

子任务编号	数据点占比	$n$
1	20%	$\le20$
2	40%	$\le1000$
3	40%	$\le10^5$

对于全部数据，保证有 $1\le n\le10^5$。