Greatest common divisor (GCD)
Given two positive integers a and b, you are asked to calculate the greatest common divisor of those. The greatest common divisor is the number that divides both a and b and is the largest of all the possible ones.
Note that the greatest common divisor of any number and 0 is that number itself.
Input
The only line of the input contains two integers a and b (0 ≤ a, b ≤ ).
Output
The program should print the greatest common divisor of a and b.
Examples
Input | Output |
|---|---|
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
Explanation
8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ the largest common is 4
54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ the largest common is 6
17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ the largest common is 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB