Recursive GCD

Given two integers a and b, write a recursive function to calculate the greatest common divisor (GCD) of a and b.

Input

The input contains two integers separated by a space a and b (1 ≤ a, b ≤ ).

Output

The program should print the GCD of a and b.

Examples

Input

Output

8 12

4

5 25

5

7 13

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