Greatest common divisor

Problem

Write a recursive gcd(a, b) using Euclid's method: gcd(a, 0) = a and gcd(a, b) = gcd(b, a % b). Read a and b and print the result.

Example

Input

48
18

Output

Divisors 1, 2, 3, 6, ...

Try the problem first. Open one hint at a time.

Hint 1

If b is 0, the answer is a.

Hint 2

Otherwise call the function again with b and a % b.

Write your Python code, run it on the examples and submit it to hidden tests.