問題文

正整数 $A,B$ が与えられます。

あなたは、$A=B$ になるまで以下の操作を繰り返します。

• $A,B$ の大小関係に応じて、次の $2$ 個のうちどちらかの処理を行う。
  • $A > B$ ならば、$A$ を $A-B$ で置き換える。
  • $A < B$ ならば、$B$ を $B-A$ で置き換える。

$A=B$ になるまで、操作を何回行うか求めてください。ただし、有限回の操作で $A=B$ になることが保証されます。

制約

• $1 \\le A,B \\le 10^{18}$
• 入力はすべて整数

入力

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

$A$ $B$

出力

答えを出力せよ。

入力例 1

3 8

出力例 1

4

始め、$A=3,B=8$ です。操作は以下のように行われます。

• $A<B$ であるため、$B$ を $B-A=5$ で置き換える。$A=3,B=5$ となる。
• $A<B$ であるため、$B$ を $B-A=2$ で置き換える。$A=3,B=2$ となる。
• $A>B$ であるため、$A$ を $A-B=1$ で置き換える。$A=1,B=2$ となる。
• $A<B$ であるため、$B$ を $B-A=1$ で置き換える。$A=1,B=1$ となる。

よって、操作回数は $4$ 回です。

入力例 2

1234567890 1234567890

出力例 2

0

入力が 32bit 整数型に収まらないことがあることに注意してください。

入力例 3

1597 987

出力例 3

15