Description

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$.

Input Format

One line containing a positive integer $n$.

Output Format

One integer representing the answer.

5

3

Hint

Sample explanation:

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