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

题目描述

小杨有一个正整数 $n$，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。

编程计算总和为 $n$ 的完全平方数的最小数量。

输入格式

输入只有一行一个正整数 $n$。对全部的测试数据，保证 $1 \leq n \leq 10^5$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

18

样例输出 #1

2

提示

无