#P134B. Pairs of Numbers

    ID: 2249 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>brute forcedfs and similarmathnumber theory*1900

Pairs of Numbers

No submission language available for this problem.

Description

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 ≤ 106).

Print the only integer k.

Input

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

Output

Print the only integer k.

Samples

5

3

1

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).