← 返回题目列表

Codeforces · 134/B

B. 数字对

中文机器翻译题面 查看原题

假设我们有一对数字 (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)。