CF343A.Rational Resistance

Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value.

However, all Mike has is lots of identical resistors with unit resistance _R_0 = 1. Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements:

1. one resistor;
2. an element and one resistor plugged in sequence;
3. an element and one resistor plugged in parallel.

With the consecutive connection the resistance of the new element equals R = R__e + _R_0. With the parallel connection the resistance of the new element equals . In this case R__e equals the resistance of the element being connected.

Mike needs to assemble an element with a resistance equal to the fraction . Determine the smallest possible number of resistors he needs to make such an element.

疯狂科学家迈克正在利用业余时间制造一台时间机器。为了完成这项工作，他需要一个具有特定电阻值的电阻器。

然而，迈克手头只有大量阻值为单位电阻 $ R_0 = 1 $ 的相同电阻器。其他阻值的元件可由这些电阻器组合而成。在本题中，我们仅将以下情形视为合法元件：

1. 单个电阻器；
2. 一个已有元件与一个电阻器串联连接；
3. 一个已有元件与一个电阻器并联连接。

在串联连接下，新元件的总电阻为 $ R = R_e + R_0 $；在并联连接下，新元件的总电阻为 $ \frac{1}{R} = \frac{1}{R_e} + \frac{1}{R_0} $，即 $ R = \frac{R_e \cdot R_0}{R_e + R_0} $。其中 $ R_e $ 表示被连接元件的电阻值。

迈克需要组装一个总电阻恰好等于分数 $ \frac{a}{b} $ 的元件。请确定他所需电阻器的最少数量。

The single input line contains two space-separated integers a and b (1 ≤ a, b ≤ 1018). It is guaranteed that the fraction is irreducible. It is guaranteed that a solution always exists.

单行输入包含两个以空格分隔的整数 $a$ 和 $b$（$1 \le a, b \le 10^{18}$）。保证分数 是最简分数。保证解一定存在。

Print a single number — the answer to the problem.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier.

输出一个数字——即该问题的答案。

在 C++ 中，请勿使用 %lld 说明符读取或写入 64 位整数。建议使用 cin、cout 流，或 %I64d 说明符。

In the first sample, one resistor is enough.

In the second sample one can connect the resistors in parallel, take the resulting element and connect it to a third resistor consecutively. Then, we get an element with resistance . We cannot make this element using two resistors.

在第一个样例中，一个电阻就足够了。

在第二个样例中，可以将两个电阻并联，再将所得元件与第三个电阻串联。这样，我们得到一个阻值为 的元件。我们无法仅用两个电阻实现该阻值。