题目描述

我们有变量 $a$ 和 $b$。初始时，$a=A$，$b=B$。

当 $a$ 和 $b$ 都大于等于 $1$ 时，Takahashi 会重复以下操作：

• 让 $g$ 是 $a$ 和 $b$ 的最大公约数，并分别用 $a-g$ 和 $b-g$ 替换 $a$ 和 $b$。

他会执行这个操作多少次？

约束条件

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

输入

输入以以下格式从标准输入中给出：

$A$ $B$

输出

打印答案。

示例输入1

15 9

示例输出1

2

开始时，$a=15$，$b=9$，然后执行以下操作：

• 让 $g=3$，并用 $12(=15-3)$ 和 $6(=9-3)$ 替换 $a$ 和 $b$。
• 让 $g=6$，并用 $6(=12-6)$ 和 $0(=6-6)$ 替换 $a$ 和 $b$。此时 $b$ 不再大于等于 $1$，所以迭代终止。

示例输入2

1 1

示例输出2

1

示例输入3

12345678910 10987654321

示例输出3

36135