Problem F: 整数拆分

Problem F: 整数拆分

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

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

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

Input

输入只有一行一个正整数 

Output

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

Sample Input Copy

18

Sample Output Copy

2