题目描述
对于一个数字对 $(a,b)$，我们可以通过一次操作把它变成新数字对 $(a,a+b)$ 或 $(a+b,b)$。
给定一个正整数 $n$，询问最少需要多少次操作可将一个数字对 $(1,1)$ 变为一个数字对，且该数字对至少有一个数是 。
输入
一个正整数 $n$。
输出
一行一个整数表示答案。
样例输入输出
提示
对于 $30\%$ 的数据，$n \leq 1000$；
对于 $60\%$ 的数据，$n \leq 2000$；
对于 $100\%$ 的数据，$n \leq 1000000$。