问题背景

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

小杨请你编写程序计算出将n拆分为完全平方数的最少数量。

问题描述

给定一个正整数n，求n拆分为完全平方数的最少数量。

格式

输入

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

输出

输出一个整数，代表把n拆分为完全平方数的最少数量。

样例

输入数据 1

18

输出数据 1

2

提示

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

对于全部数据，保证： 1 ≤ n ≤ 10^5