1588 - 辗转数对

Time Limit: 1s Memory Limit: 128MB

Submissions: 161 Solved: 28
Description
假设当前有一个数对(a, b),我们可以通过一步将这个数对变为一个新数对(a + b, b)或者是(a, a + b)。
初始的数对为(1, 1),你的任务是找到一个数字k,即通过最少的步数使得这个数对中至少一个数字等于n。
Input
输入包括多组数据,每组数据包括一行,每行有一个整数n。
Output
每组数据输出一行,每行一个整数n。
Sample Input
5
3
Sample Output
3
0
Hint
第一个样例的方法是 (1,1)  →  (1,2)  →  (3,2)  →  (5,2),共3步。
Source