编程题 1：小杨和整数拆分

题目描述
小杨有一个正整数 ( n )，他想将其拆分成若干完全平方数的和，且拆分的数量越少越好。请编写程序计算总和为 ( n ) 的完全平方数的最少数量。

输入格式
第一行：一个正整数 ( n )。

输出格式
输出一个整数，表示最少需要的完全平方数数量。

样例 1
输入：

18  

输出：

2  

解释：( 18 = 9 + 9 )，最少需要 2 个完全平方数。

数据范围

• ( 1 ≤ n ≤ $10^5$ )