完全平方数の最小個数

整数 n が与えられたとき、n の合計を作るために必要な完全平方数 (1, 4, 9, 16, 25, 36, など) の個数をできるだけ少なくする問題です。あなたなら、いくつの完全平方数を選びますか？

入力

入力として与えられるのは、単一の整数 n (1 ≤ n ≤ 60000) です。

出力

選択する完全平方数の最小個数を出力してください。

例

解説