3301: 魔法薯条
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：15
解决：9
题目描述
jzj最近学了个很实用的魔术，他可以把一个东西变少或者变多。但是由于水平还不到家，所以变多或变少的模式只有三种。 (1)、变少一个（n→ n-1） (2)、变多一个（n→ n+1） (3)、变为原来的p次幂(p为任意正整数)。（n→n^p） Jzj喜欢吃薯条，一包薯条jzj不停地吃啊吃，最后只剩下了一根。但是jzj舍不得把剩下的一根一口就吃掉，所以他想用他的小魔法把薯条变得越来越多越来越多~ 可是薯条吃太多，jzj的肚子也撑不下，所以jzj订好了计划，他只能再吃n根薯条，少吃一根jzj会不开心，多吃一根jzj的肚子会撑坏，所以jzj只能恰好吃n根薯条。 Jzj想尽快的吃到这n根薯条，所以他想知道他最少需要施展几次魔法能够把1根薯条变为n根。
输入
一行一个正整数N，表示jzj恰好能吃N根薯条。
输出
一行一个整数，表示从1变到N最少施展的魔法次数。
样例输入 复制
8样例输出 复制
2提示
【输入样例】 80
【输出样例】 4
样例解释： 对于第一个样例，jzj第一次施法完成效果1，现在jzj就有了2根薯条，之后施用魔法完成效果3（我们令p=3），就变出了8根薯条。 对于第二个样例，步骤如下： 1: 1+1 → 2 2: 2+1 → 3 3: 34 → 81 4: 81-1 → 80
【数据规模】 对于30%的数据满足 N≤20 对于60%的数据满足 N≤1000 对于100%的数据满足 1≤N≤1000000