题目描述

给你一个整数$n$，请输出和为$n$的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方，比如$1, 4, 9, 16$均为完全平方数而$3, 11$则不是完全平方数。

样例输入

输入一行仅一个整数$n$。

样例输出

输出一个答案。

样例

样例一

12

3

样例解释：$12 = 4 + 4 + 4$。

数据范围

$1 \le n \le 10^{4}$