题目描述

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

小杨请你编写程序计算出总和为 m 的完全平方数的最少数量。

输入格式

第一行包含一个正整数 m，含义如题面所示。

输出格式

输出一个整数，代表总和为 m 的完全平方数的最少数量。

样例

样例输入 1

18

样例输出 1

2

样例解释

18=9+9=16+1+1，其中最少需要 2 个完全平方数。

数据范围

对于 20% 的测试点，保证 m≤20；对于 40% 的测试点，保证 m≤1000；对于全部数据，保证 1≤m≤10^5。