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.

备注:

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