描述

对于一个数字对\((a, b)\)，我们可以通过一次操作将其变为新数字对\((a+b, b)\)或\((a, a+b)\)。

给定一正整数\(n\)，问最少需要多少次操作可将数字对\((1, 1)\)变为一个数字对，该数字对至少有一个数字为\(n\)。

格式

输入格式

第一行一个正整数 \(n\)。

输出格式

一个整数表示答案。

样例1

输入样例1

5

输出样例1

3

样例解释

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

限制

对于\(100\)%的数据，\(1 <= n <= 10^6\)。