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

  1. 8 β†’ 1, 2, 4, 8 |||| 12 β†’ 1, 2, 3, 4, 6, 12 β‡’ the largest common is 4
  1. 54 β†’ 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 β†’ 1, 2, 3, 4, 6, 12, 24 β‡’ the largest common is 6
  1. 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

To check your solution you need to sign in
Sign in to continue