Description

给定两个正整数，求它们的最大公约数。

Input

输入一行，包含两个正整数(<1,000,000,000)。

Output

输出一个正整数，即这两个正整数的最大公约数。

Samples

6 9

3

说明

求最大公约数可以使用辗转相除法： 假设 a > b > 0，那么a 和 b 的最大公约数等于 b 和 a%b 的最大公约数，然后把 b 和 a%b 作为新一轮的输入。 由于这个过程会一直递减，直到 a%b 等于 0 的时候，b 的值就是所要求的最大公约数。 比如： 9 和 6 的最大公约数等于 6 和 9%6=3 的最大公约数。 由于 6%3==0，所以最大公约数为3。