5542 - GESP:2024-9月等级6-T1-小杨和整数拆分
Time Limit : 1 秒
Memory Limit : 128 MB
小杨有一个正整数n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好 小杨请你编写程序计算出总和为n的完全平方数的最少数量
Input
第一行包含一个正整数n
Output
输出1个整数，代表总和为n的完全平方数的最少数量
Examples
Input
18
Output
2
Hint
样例1解释 18=9+9=16+1+1 ,其中至少需要2个完全平方数
数据1<=n<=10^5