当前没有测试数据。

3.数字对

题目描述

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

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

输入格式

一个正整数$n$。

输出格式

一行一个整数表示答案。

数据范围与提示

• 对于$30\%$的数据，$n < 1000$；
• 对于$60\%$的数据，$n < 20000$；
• 对于$100\%$的数据，$n < 1000000$。

样例

5

3