Description

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

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

Input Format

一行一个正整数 $n$。

Output Format

一个整数表示答案。

5

3

Hint

样例解释：

对于 $30\%$ 的数据，$1 \le n \le 1000$。

对于 $60\%$ 的数据，$1 \le n \le 20000$。

对于 $100\%$ 的数据，$1 \le n \le 10^6$。