背景

GESP六级真题(202409)

描述

⼩杨有⼀个正整数 $n$ ，⼩杨想将它拆分成若⼲完全平⽅数的和，同时⼩杨希望拆分的数量越少越好。

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

格式

输入

第⼀⾏包含⼀个正整数 $n$ ，含义如题⾯所⽰。

输出

输出⼀个整数，代表总和为 $n$ 的完全平⽅数的最少数量。

样例

18

2

样例解释

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

数据规模

对于全部数据，保证有 $1 \le n \le 10^5$。

限制

时间限制：1.0 s

空间限制：512.0 MB