问题描述

对于一个数字对(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。