Pairs of Numbers
Time Limit:1000MS Memory Limit:65535KB
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).Process to the end of file.
Print the only integer k.