Euclid

The famous Euclidean algorithm is found in Book VII of the Elements. The Elements was written in 300 B.C. by the Greek mathematician Euclid. It is rumored that King Ptolemy, having looked through the Elements, hopefully asked Euclid if there were not a shorter way to geometry, and that Euclid answered sternly: "In geometry there is no royal road!" Probably we should not blame the King for looking for short cuts, because there are thirteen books in the Elements. The books consist mainly of the mathematical knowledge Euclid amassed, and possibly some discoveries of his own. His great achievement is the beautifully systematic presentation of that material as an organic whole. The Elements remained a standard work for over two thousand years.

The original Euclidean algorithm uses subtraction to find the greatest common divisor (gcd) of two positive integers $A$ and $B$. It is based on the observation that a common divisor of $A$ and $B$ is also a common divisor of $\min(A, B)$ and $\max(A, B) - \min(A, B)$. So the gcd of $A$ and $B$ is found like this.

1. If $A = B$, the gcd is $B$ and the algorithm ends.
2. Replace $A$ by $\max(A, B) - \min(A, B)$, and $B$ by $\min(A, B)$. Go to step 1.

With the original Euclidean algorithm or otherwise, find the gcd of two positive integers.

For $A = 24$ and $B = 15$, the original Euclidean algorithm walks through these values.

1. $A = 24 - 15 = 9$, $B = 15$
2. $A = 15 - 9 = 6$, $B = 9$
3. $A = 9 - 6 = 3$, $B = 6$
4. $A = 6 - 3 = 3$, $B = 3$

That is, $\gcd(24, 15) = 3$.

The input contains one line. The line contains two positive integers separated by a space, each not larger than 32767.

Print one integer, the gcd of the two given positive integers.