Euclidean Algorithm ⭐⭐⭐

What is the Euclidean algorithm?

The Euclidean algorithm computes the Greatest Common Divisor (GCD) of two integers. The GCD is the largest number that divides both exactly.

The key idea: the GCD of a and b equals the GCD of b and the remainder of a / b. This repeats until the remainder is 0, at which point a holds the GCD.

GCD(12, 8) → GCD(8, 4) → GCD(4, 0) → result: 4

The algorithm in pseudocode:

while b != 0:
    temp = b
    b = a % b
    a = temp
result = a

Task

Read two integers a and b and compute their GCD using the Euclidean algorithm.

Input

Two integers on the same line:

1. a
2. b

Output

Print the Greatest Common Divisor of a and b.

Examples

Input:

12 8

Output:

4

Input:

15 5

Output:

5