Minimum Operations to Reach a Number Pair

Consider a pair of positive integers \( (a, b) \). In one operation you can transform \( (a, b) \) into either \( (a+b, b) \) or \( (a, a+b) \). Starting from \( (1,1) \), you are allowed to perform these operations repeatedly. Given a positive integer \( n \), determine the minimum number of operations required to obtain a pair where at least one of the numbers is equal to \( n \).

The operations can be thought of in reverse. Notice that if a pair \( (a, b) \) (with \( a \neq b \)) is generated by the above operations, then it can be uniquely reduced (by a single subtraction per operation) back to \( (1,1) \) via the recurrence:

[ T(a,b)=\begin{cases}0, & (a,b)=(1,1),\ 1+T(a-b,b), & a>b,\ 1+T(a,b-a), & b>a.\end{cases} ]

In particular, for any reachable pair \( (x,y) \) where \( \max(x,y)=n \) and \( \gcd(x,y)=1 \), the value \( T(x,y) \) equals the number of subtractions required to reduce it to \( (1,1) \). Equivalently, if we simulate the Euclidean algorithm by repeated subtraction, the number of operations is equal to the sum of the division quotients (with a final adjustment of subtracting one). For example:

• For \( (6,1) \): We have \( 6/1=6 \) and thus the number of operations is \( 6-1=5 \).
• For \( (7,2) \): We have \( 7/2=3 \) with remainder 1 and then \( 2/1=2 \), so the total operations are \( 3+2-1=4 \).

Your task is to, given \( n \), compute the minimum number of operations needed to obtain a pair \( (x,y) \) with \( x=n \) or \( y=n \) (and \( \gcd(x,y)=1 \)), by considering every valid \( m \) (where \( m < n \)) such that either \( (n, m) \) or \( (m, n) \) is reachable from \( (1,1) \).

Note: When \( n=1 \), the answer is \( 0 \) since \( (1,1) \) is already the starting pair.

inputFormat

The input consists of a single line containing a positive integer \( n \) (\( 1 \le n \le 10^5 \), for example).

outputFormat

Output a single integer representing the minimum number of operations required to reach a pair in which at least one number is equal to \( n \).

sample

1

0