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