P2090 数字对

对于一个数字对 $(a,b)$，我们可以通过一次操作将其变为新数字对 $(a+b,b)$ 或 $(a,a+b)$。 给定一正整数 $n$，问最少需要多少次操作可将数字对 $(1,1)$ 变为一个数字对，该数字对至少有一个数字为 $n$。

一行一个正整数 $n$。

一个整数表示答案。

样例解释： $$(1,1)  \to  (1,2)  \to  (3,2)  \to  (5,2)$$ --- 对于 $30\%$ 的数据，$1 \le n \le 1000$。 对于 $60\%$ 的数据，$1 \le n \le 20000$。 对于 $100\%$ 的数据，$1 \le n \le 10^6$。