题目描述

一个电阻器 $R_0$ 的电阻是 $1$（即 $R_0 =\frac{1}{1}$），一个电阻元件（电阻为 $R_e$，可以是电阻器）和另外一个电阻器 （电阻为 $R_0$）可以有如下的两种合成方式，合成一个电阻元件

• 串联：排成一行，组合后的电阻为 $R=R_0+R_e$；
• 并联：排成一列，组合后的电阻为 $R=\frac{1}{\frac{1}{R_0} + \frac{1}{R_e}}$。

例如，两个电阻器用第一种方式合成，电阻为 $R=R_0+R_e = 1+1 =2$。

再用合成后的电阻元件与另一个电阻器用第二种方式合成，电阻为 $R=\frac{1}{\frac{1}{R_0} + \frac{1}{R_e}}=\frac{1}{\frac{1}{1} + \frac{1}{2}} = \frac{2}{3}$。 ​

给出 $a,b\ (1≤a,b≤10^{18})$，求最少用多少个电阻器能合成一个电阻为 $\frac{a}{b}$ 的电阻元件？

输入格式

两个整数 $a,b$，$1\le a,b\le 10^{18}$，保证 $\frac{a}{b}$ 已经最简，保证有解。

输出格式

一个整数表示答案。

1 1

1

3 2

3

199 200

200