Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC). ×

B. Pairs of Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

The input contains the only integer n (1 ≤ n ≤ 106).

Output

Print the only integer k.

Examples
Input
5
Output
3
Input
1
Output
0
Note

The pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1)  →  (1,2)  →  (3,2)  →  (5,2).