题目描述

假设有一个数对 $(a, b)$。一步之内，我们可以把它变成 $(a+b, b)$ 或 $(a, a+b)$。

初始数对是 (1,1)。你的任务是求出最小的步数 $k$，使得 (1,1) 能经过 $k$ 步变成一个至少有一个数等于 $n$ 的数对。

输入格式

输入只包含一个整数 $n$（$1 \le n \le 10^6$）。

输出格式

输出一个整数 $k$。

5

3

1

0

说明/提示

数对 (1,1) 可以经三步变成含 5 的数对：(1,1) → (1,2) → (3,2) → (5,2)。