题目描述：

Will经过不懈寻觅，终于发现了一个SuperPPMM，好吧，Will要去追MM了！！

这个SuperPPMM真的是很PP，长的像花仙子一样，也很喜欢花。虽然Will觉得结识这个MM没多久就送礼物，有点让Will觉得不大好意思，但是在hyf，QB，还有小msh等人的鼓励之下，Will决定寻找机会送MM一个大大的礼物给MM。送什么呢？当然是送MM最喜欢的花啦，Will准备送很多很多漂亮的花给MM，这样的一个大大的惊喜，一定会让MM对Will的好感值迅速大增，甚至超过MaxLongint然后越界再达到MaxLongint～

送花的前提当然是得有花，而大家知道买花是很贵的，当然一小点花的价钱还是没什么的，但是如果Will要送很多很多的花，那这就……不过Will是很厉害的，不光精通理论，还很懂得动手实践，绝对是新一代好青年！要知道，Will最近在家闭门修炼，偶然学会了一种变花的魔法，有了这种魔法，Will只要买一枝花，就能变出很多很多的花啦！（hyf：这么神奇！也帮我变点，我去送MM！ 小msh：一点都没rpk送我的花漂亮～ QB：唔……（走神中，估计又思春了） jzt：花有什么好变的，还不如变肯德基……）

Will的魔法是这样的：假设当前Will一共有m枝花，一旦Will施用一次魔法，可以完成如下效果中的任意一种：

(1) 使一枝花消失，也就是施用后Will有m-1枝花；

(2) 变出一枝花，也就是施用后Will有m+1枝花；

(3) 使得Will拥有的花的数量是原来的p次幂，也就是施用后Will有mp枝花（这里p可以为任意正整数）。

显然啦，任意时刻Will手上都是有花的——如果没有花，Will怎么施魔法呢？

Will经过反复琢磨，选定了一个最有意义的数字N，“嗯，就送N枝花给MM吧！”Will决定了。施用魔法是一个很累人的事情，所以Will想知道他至少需要施用多少次魔法呢？

问题：

给定N，一开始Will有1枝花，求最少施用魔法次数，使得变出N枝花。 输入

一行一个正整数，N。 输出

一行一个整数，表示最少施用魔法的次数。 样例输入

8

样例输出

2