题目描述

変数 $a,b$ があり、初め $a=A,\ b=B$ です。

高橋君は $a,b$ がともに $1$ 以上の間、次の操作を繰り返すことにしました。

• $a$ と $b$ の最大公約数を $g$ とする。そして、$a,b$ をそれぞれ $a-g,b-g$ に置き換える。

操作は何回行われますか。

输入格式

入力は以下の形式で標準入力から与えられる。

$A$ $B$

输出格式

答えを出力せよ。

题目大意

给出两个整数 $a,b$。当 $a, b$ 均为正数时，重复执行以下操作：

• 令 $g = gcd(a,b)$。
• $a \to a-g,b \to b-g$。

问将会执行多少次操作？

15 9

2

1 1

1

12345678910 10987654321

36135

提示

制約

• $1\ \leq\ A,B\ \leq\ 10^{12}$
• $A,B$ は整数

Sample Explanation 1

$a=15,b=9$ の状態から以下のように操作が行われます。 - $g=3$ とする。そして、$a,b$ がそれぞれ $12(=15-3),6(=9-3)$ に置き換えられる。 - $g=6$ とする。そして、$a,b$ がそれぞれ $6(=12-6),0(=6-6)$ に置き換えられる。$b$ が $1$ 以上でなくなったため、操作の繰り返しはここで終了する。