Pairs of Numbers

题目背景

重题请做P2090

题目描述

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^{6} $ ).

输出格式


Print the only integer $ k $ .

输入输出样例

输入样例 #1

5

输出样例 #1

3

输入样例 #2

1

输出样例 #2

0

说明

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