K. 这是一道简单题

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

这是一道简单题：

给你一个整数 n ，把n拆分成若干数的和，要求每个数都是完全平方数。请你找到一种最拆分出的数的个数最少的方法，输出这个方法拆分的数的最少个数

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

时间限制：1s

空间限制：256MIB

输入格式：两行，各一个字符串。

输出格式：一个整数，代表个数

数据范围：n<=10000

Input

输入：12

Ouput

输出：3

样例解释：12=4+4+4，4=2*2.