Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
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).