Description

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

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

Input Format

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

Output Format

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

18

2

Hint

样例解释

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

数据范围

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

Source

GESP六级202409