假设我们有一对数字 (a, b)。我们可以一步从给定的对中得到一个新的对 (a + b, b) 或 (a, a + b)。
设初始数字对为 (1,1)。你的任务是找到数字 k,即将 (1,1) 转换为至少有一个数字等于 n 的对所需的最少步骤数。
输入
输入包含唯一的整数 n (1 ≤ n ≤ 106)。
输出
打印唯一的整数 k。
示例
输入 #1
5
输出 #1
3
输入 #2
1
输出 #2
0
注意
对 (1,1) 可以通过三步转变成包含 5 的对:(1,1) → (1,2) → (3,2) → (5,2)。