该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 3D. calculator

时间限制：$1s$

空间限制：$64MB$

题目描述

最近，$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)$的计算次数明显是更少的，只需要$2$次。

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

数据格式

输入

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

输出

一个正整数$k.$

样例1

输入

5

输出

3

样例2

输入

1

输出

0

样例解释

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