数字对
题目描述
对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。
给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。
输入输出格式
输入格式
第一行一个正整数 n
输出格式
一个整数表示答案。
输入输出样例
输入样例 #1
5输出样例 #1
3说明
样例解释：
(1,1) → (1,2) → (3,2) → (5,2)
对于30%的数据， 1 <= n <= 1000
对于60%的数据， 1 <= n <= 20000
对于100%的数据，1 <= n <= 10^6