题目描述

让我们假设有一对数 $(a,b)$。我们可以从前一步得到后一对数 $(a+b,b)$ 或者 $(a,a+b)$。

让我们规定一开始这对数为 $(1,1)$。你的任务就是找到数 $k$，使 $k$ 为从 $(1,1)$ 转换到一对至少含有一个 $n$ 的数对的最少步骤。

输入格式

输入只包括一个整数 $n\ (1\le n\le 10^6)$。

输出格式

输出唯一的整数 $k$。

5

3

1

0