题目描述

小杨有一个正整数 $n$，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。 小杨请你编写程序计算出总和为 $n$ 的完全平方数的最少数量。

输入格式

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

输出格式

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

样例

输入样例 1

18

输出样例 1

2

样例解释 1

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$。