Greatest Common Divisor

A builder wants to cover a floor 48 cm by 18 cm with identical square tiles, without cutting any. The biggest tile that works is 6 cm, because 6 is the largest number that divides both 48 and 18. That number is their greatest common divisor (GCD).

Write gcd(a, b) that returns the greatest common divisor of two non-negative integers a and b. Every number divides 0, so when one of them is 0 the answer is the other one.

Examples

gcd(48, 18)    # returns 6
gcd(17, 5)     # returns 1
gcd(0, 9)      # returns 9

Constraints

• 0 <= a, b <= 10^18, and they are not both 0

Note

Python has math.gcd, but try writing it yourself. Some tests use numbers with 19 digits, so testing every possible divisor one by one is far too slow.