最大公约数

最大公约数

Description

给出两个正整数A,B,求它们的最大公约数。

Format

Input

第一行输入正整数A,第二行输入正整数B。

Output

在第一行输出一个整数,表示A,B的最大公约数。

Sample 1

Input

18
24

Output

6

Limitation

1s, 128MiB for each test case.

在60%的数据中,1<=A,B<=10^18;
在100%的数据中,1<=A,B<=10^3000

Source