Problem Statement

We have variables $a$ and $b$. Initially, $a=A$ and $b=B$.

Takahashi will repeat the following operation while both $a$ and $b$ are greater than or equal to $1$.

• Let $g$ be the greatest common divisor of $a$ and $b$, and replace $a$ and $b$ with $a-g$ and $b-g$, respectively.

How many times will he perform the operation?

Constraints

• $1 \leq A,B \leq 10^{12}$
• $A$ and $B$ are integers.

Input

The input is given from Standard Input in the following format:

A B

Output

Print the answer.