题目描述

yhx 最近在玩一个游戏，在这个游戏里他一开始只有 1 点生命值

但是这个游戏允许他进行几轮操作来增加他的生命值

每一轮游戏他可以选择以下三种操作之一进行： 假设现在他现在的生命值为 $x$

1. 当前生命值 $+1$，即 $x + 1$
2. 当前生命值 $-1$，即 $x - 1$
3. 使得生命值变成当前生命值的 $y$ 次方($y$ 可以是任意正整数)，即 $x^y$

当前，任何时间 yhx 的生命值都不能为 $0$ ，否则游戏会失败

现在 yhx 希望自己的游戏不那么无聊，所以他不希望生命值越大越好，他自己设置了一个想要的生命值 $N$

现在他想知道，最少进行几轮操作可以使得他的生命值为 $N$？

输入格式

一行一个正整数 $N$

输出格式

一行一个整数，表示最少进行的操作次数

数据范围

对于 $60\%$ 的数据保证 $1 \leq N \leq 20$

对于 $100\%$ 的数据保证 $1 \leq N \leq 100$

样例输入

80

样例输出

4

样例解释

四次步骤分别如下：

1. $1 + 1 = 2$
2. $2 + 1 = 3$
3. $3^4 =81$
4. $81-1 = 80$