CF134B.Pairs of Numbers

Let's assume that we have a pair of numbers (a, b). We can get a new pair (a + b, b) or (a, a + b) from the given pair in a single step.

Let the initial pair of numbers be (1,1). Your task is to find number k, that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals n.

假设我们有一对数字 $(a,\,b)$。在一步操作中，我们可以从给定的数对得到新数对 $(a + b,\,b)$ 或 $(a,\,a + b)$。

设初始数对为 $(1,1)$。你的任务是求出数字 $k$，即从 $(1,1)$ 出发，经过最少多少步操作后，能得到一个至少有一个数等于 $n$ 的数对。

The input contains the only integer n (1 ≤ n ≤ 106).

输入仅包含一个整数 $n$（$1 \leq n \leq 10^6$）。

Print the only integer k.

输出唯一的整数 $k$。

The pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1)  →  (1,2)  →  (3,2)  →  (5,2).

数对 $(1,1)$ 可以通过三步变换得到一个包含 $5$ 的数对：$(1,1) \rightarrow (1,2) \rightarrow (3,2) \rightarrow (5,2)$。