题目描述

给定正整数 $A$ 和 $B$。

你要重复以下操作，直到 $A=B$：

• 比较 $A$ 和 $B$，执行以下两种操作之一：
  • 如果 $A > B$，将 $A$ 替换为 $A-B$；
  • 如果 $A < B$，将 $B$ 替换为 $B-A$。

你将重复多少次操作直到 $A=B$？保证有限次重复将使得 $A=B$。

约束条件

• $1 \leq A,B \leq 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$。

因此，你重复了四次。

示例输入 2

1234567890 1234567890

示例输出 2

0

注意输入可能无法适应 32 位整数类型。

示例输入 3

1597 987

示例输出 3

15