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*.
The input contains the only integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>).
5
3
1
0
2
1
3
2
4
3
10
5
1009
15
2009
17
7009
19
9009
20
19009
21
29009
22
12434
21
342342
28
342235
28
362235
28
762235
30
878235
30
978235
30
1000000
30
6
5
10000
20
999999
30
524287
29
777777
30
123756
26
976438
30
434563
28
345634
28
65457
24
123456
26
999997
30
98989
25
8
4
123455
26
990001
30
123141
26
998
16
453422
28
623423
29
89
9
24234
23
999879
30
345612
28
998756
30
999989
30
999998
30
999912
30
100000
25
def solve(n):
    ans = n - 1
    for i in range(2, n // 2 + 1):
        j = n
        k = 0
        while i > 1 and j > 1:
            k += 1
            if j >= i:
                j -= i
            else:
                i -= j
        if i < 1 or j < 1:
            continue
        elif i == 1:
            ans = min(ans, k + j - 1)
        elif j == 1:
            ans = min(ans, k + i - 1)
    return ans

if __name__ == "__main__":
    ans = solve(int(input()))
    print(ans)