A famous algorithm for finding the greatest common divisor of two numbers is Euclid's algorithm. The algorithm works like this:

get the remainder of num1 / num2.
set num1 to num2.
set num2 to the remainder found above.
repeat while num2 is not zero.

Input

There will be two lines of input each containing a positive integer no greater then 1 million.

Output

Print the greatest common divisor of the numbers.

Sample Input

4
6

Sample Output

2