CF134B 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

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