题目描述

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

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

输入格式

输入包含唯一的整数 $n (1 \le n \le 10^6)$

输出格式

打印唯一的整数 $k$

样例

5

3

样例2

1

0

(1,1) 可以通过三步转化为包含 5 ：(1,1) → (1,2) → (3,2) → (5,2)