\(calculator\)

时间限制：\(1s\)

空间限制：\(32MB\)

题目描述

最近，\(jrm\)自己设计了一套计算器，但是有一点点不同。\(jrm\)介绍，在他的计算器中，加法需要以二元组\((a,b)\)的形式输入，而输出的结果是\((a,a+b)\)和\((a+b,b)\)两个二元组。无论如何，这个思路确实没有什么问题，所以就要测试结果的精确性了。测试的方法是这样的，先输入\((1,1)\)，那么第一次理论的结果就是\((1,2)\)和\((2,1)\)，然后我们可以选择\((1,2)\)再输入，那么第二次的理论结果就是\((1,3)\)和\((3,2)\)，当然如果选择了\((2,1)\)输入，那么第二次的理论结果就是\((2,3)\)和\((3,1)\)。

聪明的你一定可以发现，如果你想要最后的结果中含有\(n\)，一般都可以通过多种方式获得。比如说你想要最后结果含有\(3\)，就有\((1,3),(3,2),(4,3)\)等多种情况。而\((1,3),(3,2)\)的计算次数明显是更少的，只需要\(1\)次。

由于\(jrm\)刚刚从西安回来，想要更多的休息时间，所以希望你可以帮助他计算结果中含有\(n\)的最少计算次数\(k\)。

数据格式

输入

一个正整数\(n\)，\((1 \le n \le 10^6)\).

输出

一个正整数\(k.\)

样例

输入

5

输出

3

样例

输入

1

输出

0

样例解释

\((1,1)\rightarrow(1,2)\rightarrow(3,2)\rightarrow(5,2)\)

数据范围及约定

\(20\%\)的数据，\(n \le 20\).

所有数据，\(n \le 10 ^ 6\).