仅供参考，限于本人记忆力有限可能与原版本有出入，题目描述仅保证题意基本正确。由于C++与Python语言运行速度不同数据减弱且时限放宽。

Description

小杨想将一个数分解为尽可能少的平方数之和。平方数定义为一个整数的平方，例如 $1=1^2,9=3^2,16=4^2$，所以 $1,4,16$ 都是平方数。

小杨要求满足条件的最小分解个数，例如 $18=16+1+1=9+9$，则 $18$ 的满足条件的最小分解个数为 $2$。

Format

Input

一个整数 $n$。

Output

一个整数，表示 $n$ 的满足条件的最小分解个数。

Samples

18

2

Limitation

对于 $30\%$ 的数据，$1\leq n \leq 300$。

对于 $50\%$ 的数据，$1\leq n \leq 1000$。

对于 $100\%$ 的数据，$1\leq n \leq 30000$。

时限2000ms。

C++原数据为 $1\leq n \leq 100000$，1000ms。