疯狂科学家迈克正在业余时间建造一台时间机器。为了完成这项工作,他需要一个具有一定阻值的电阻。
然而,Mike 拥有的只是许多单位电阻 R0 = 1 的相同电阻器。可以用这些电阻器构建具有其他电阻的元件。在这个问题中,我们将考虑以下元素:
1.电阻1个;
2.依次插入一个元件和一个电阻;
3. 并联插入一个元件和一个电阻。
连续连接后,新元件的电阻等于 R = Re + R0。通过并联连接,新元件的电阻等于 $$R = \frac{1}{\frac{1}{R_{e}} + \frac{1}{R_{0}}}$$。在这种情况下,Re 等于所连接元件的电阻。
Mike 需要组装一个电阻等于分数 $${ \frac { a } { b } }$$ 的元件。确定制作这样一个元件所需的尽可能少的电阻器数量。
输入
单个输入行包含两个空格分隔的整数 a 和 b (1 ≤ a, b ≤ 1018)。保证分数 $${ \frac { a } { b } }$$ 是不可约的。保证解总是存在。
输出
打印一个数字——问题的答案。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。建议使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
1 1
输出 #1
1
输入 #2
3 2
输出 #2
3
输入 #3
199 200
输出 #3
200
注意
在第一个示例中,一个电阻就足够了。
在第二个示例中,可以并联连接电阻器,取出所得元件并将其连续连接到第三个电阻器。然后,我们得到一个电阻为 $$\frac{1}{\frac{1}{1}+\frac{1}{1}}+1=\frac{3}{2}$$ 的元素。我们不能使用两个电阻来制作这个元件。