Problem I
Euclid's GCD

One of the oldest known algorithms is a method for finding the greatest common divisor of two natural numbers. It turns out that you have already learned all you need to implement it.

Given two numbers $a$ and $b$, we keep doing the following until $b$ becomes $0$:

• Calculate the remainder of dividing $a$ by $b$,

• update $a$ to be the previous value of $b$ and $b$ to be the value of the remainder.

If at any time $b$ is $0$, then $a$ is the greatest common divisor of the original two numbers.

Input

Input consists of two lines. The first line consists of one integer $a$, where $0\le a\le {10}^{18}$. The second line consists of one integer $b$, where $0\le b\le {10}^{18}$.

Output

Output the greatest common divisor of $a$ and $b$.

0
3

3

12
15

3

15
28

1

204
564

12

1495
715

65