题目描述

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

18

样例输出 #1

2

提示

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

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