题目描述

有两个变量 $a, b$，初始时 $a = A, b = B$。

高桥君决定在 $a, b$ 都大于等于 $1$ 的情况下，反复进行如下操作：

• 取 $a$ 和 $b$ 的最大公约数为 $g$。然后，将 $a, b$ 分别替换为 $a-g, b-g$。

操作会被执行多少次？

输入格式

输入以以下格式从标准输入读入。

$A$ $B$

输出格式

请输出答案。

样例 1

输入

15 9

输出

2

样例 2

输入

1 1

输出

1

样例 3

输入

12345678910 10987654321

输出

36135

说明/提示

限制条件

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

样例解释 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$，操作在此结束。

由 ChatGPT 4.1 翻译