### 问题描述

小蓝有一种超能力，对于一个数字对 $(a,b)$，他可以通过使用一次超能力将其变为新数字对 $(a+b,b)$ 或 $(a,a+b)$。

现在，给定一正整数 $n$，问小蓝最少需要使用多少次超能力，才可将数字对 $(1, 1)$ 变为一个至少有一个数字为 $n$ 的数字对。

输入格式

输入包含一个整数 $n$，含义见上文。

输出格式

输出一个整数，表示小蓝使用超能力的最少次数。

样例输入

5

样例输出

3

评测数据规模

对于所有评测数据，$1\leq{n}\leq{10^6 }$。