B. Pairs of Numberstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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.InputThe input contains the only integer n (1 ≤ n ≤ 106).OutputPrint the only integer k.ExamplesInput5Output3Input1Output0NoteThe pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1)  →  (1,2)  →  (3,2)  →  (5,2).
Input5
Output3
['brute force', 'dfs and similar', 'math', 'number theory', '*1900']