#P2090. 数字对

数字对

题目描述

对于一个数字对(a, b),我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。

给定一正整数n,问最少需要多少次操作可将数字对(1, 1)变为一个数字对,该数字对至少有一个数字为n。

输入格式

第一行一个正整数 n

输出格式

一个整数表示答案。

5
3

提示

样例解释:

(1,1)  →  (1,2)  →  (3,2)  →  (5,2)

对于30%的数据, 1 <= n <= 1000

对于60%的数据, 1 <= n <= 20000

对于100%的数据,1 <= n <= 10^6