g6-07873. 完全平方数最少个数 未做

给定一个正整数 $n$，把 $n$ 拆成若干个完全平方数之和，求最少需要几个完全平方数。$1$ 也是完全平方数。

一行一个整数 $n$。

一行一个整数，表示最少需要的完全平方数个数。

输入 1

12

输出 1

3

对于所有数据，$1\le n\le 100000$。