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

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

该数字对至少有一个数字为 n。

样例解释

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

数据范围

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

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

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