小杨和整数拆分

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

输入格式

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

输出格式

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

样例

样例输入：

12

其中最少需要 3 个完全平方数（4 + 4 + 4）。

样例输出：

3

数据范围

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