Write a program that computes the greatest common divisor of two numbers.

Input

Input consists of two strictly positive natural numbers a and b.

Output

Print the greatest common divisor of a and b.

Observation

Although the solution to this exercise does not need to be very efficient, it should not be too slow.

Public test cases

**Input**

16104 3216

**Output**

The gcd of 16104 and 3216 is 24.

**Input**

1107 15129

**Output**

The gcd of 1107 and 15129 is 369.

Information

- Author
- Jordi Petit
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Java Python
- User solutions
- C C++ Java Python Rust