Description

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

Input Format

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

Output Format

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

18

2

Hint

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