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
import abc
import itertools
import math
from math import gcd as gcd
import sys
import queue
import itertools
from heapq import heappop, heappush
import random
from array import array
from bisect import *

# input = lambda: sys.stdin.buffer.readline().decode().strip()
# inp = lambda dtype: [dtype(x) for x in input().split()]
debug = lambda *x: print(*x, file=sys.stderr)
ceil1 = lambda a, b: (a + b - 1) // b
Mint, Mlong, out = 2 ** 31 - 1, 2 ** 63 - 1, []

squares = []
for i in range(0, 520):
    squares.append(i * i)


def solve():
    def gcd(a, b):
        if min(a, b) == 1:
            return max(a, b) - 1

        if a < b:
            a, b = b, a

        if a % b == 0:
            return 1 << 60
        return a // b + gcd(a % b, b)

    n = int(input())
    mn = n - 1

    for p in range(1, n):
        mn = min(mn, gcd(p, n))

    print(mn)


if __name__ == '__main__':
    multi_test = 0

    if multi_test == 1:
        t = int(sys.stdin.readline())
        for _ in range(t):
            solve()
    else:
        solve()
