Algorithms and Data Structures

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: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in