题目描述

小樱喜欢玩弄计算器,尤其是用计算器加加减减的凑出某个特定的数字。 终于有一天,计算器在高强度的工作下坏掉了,只剩下两个可用的键:加一键和平方键。 也就是说,如果目前计算器显示的数字是x,那么按下加一键将x变为$x+1$, 按下平方键使得x变为$x^2$。 小樱想要从0开始凑出来一个特定的数字n,可她不会用加减之外的按钮了。请你帮帮她求出凑出n最少需要按几次按钮。

输入格式

一行一个非负整数n。

输出格式

一行一个非负整数ans,表示最少需要按几次按钮。

输入输出样例

20

8

说明/提示

样例解释：

最少需要 8 次操作:

按 + 1 变成 1

按 + 1 变成 2

按平方变成 4

按平方变成 16

按四次 + 1 变成 20

数据范围：

对于 10% 的数据 $1≤n≤20$

对于 30% 的数据 $1≤n≤10^6$

对于 50% 的数据 $1≤n≤10^9$

对于 100% 的数据 $1≤n≤10^{18}$