P2090 Number Pair

For a number pair $(a, b)$, in one operation we can transform it into $(a+b, b)$ or $(a, a+b)$. Given a positive integer $n$, find the minimum number of operations to transform the pair $(1, 1)$ into a pair in which at least one number is $n$.

One line containing a positive integer $n$.

One integer representing the answer.

Sample explanation: $$(1,1)  \to  (1,2)  \to  (3,2)  \to  (5,2)$$ For $30\%$ of the testdata, $1 \le n \le 1000$. For $60\%$ of the testdata, $1 \le n \le 20000$. For $100\%$ of the testdata, $1 \le n \le 10^6$. Translated by ChatGPT 5