该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

强哥最近迷上了建筑，他决定用砖块搭建一个金字塔。每一层金字塔都必须由相同大小的正方形砖块组成，而且砖块的大小必须是某个整数的平方（比如 1×1、2×2、3×3……）。强哥手头有一堆总面积为 $n$ 的砖块，但他希望用尽可能少的砖块来搭建金字塔。

比如，如果 $n=18$，强哥可以用：

• 两块 3×3 的砖（因为 $3×3 + 3×3 = 9 + 9 = 18$），
• 或者一块 4×4 的砖加上两块 1×1 的砖（$16 + 1 + 1 = 18$），但这样就需要 3 块砖，不如第一种方法划算。

你的任务是帮强哥计算出，搭建总面积为 $n$ 的金字塔，最少需要多少块砖？

输入格式

第一行包含一个正整数 $n$，表示强哥需要的金字塔总面积。

输出格式

输出一个整数，表示最少需要的砖块数量。

样例

输入1

18

输出1

2

数据范围

保证所有测试数据满足 $1 \leq n \leq 10^5$。