Background

Description

输入两个正整数，输出最大公约数(辗转相除法)。

辗转相除法步骤如下：

1.选择两个整数a和b。

2.用a除以b，得到余数r。

3.将b的值赋给a，将r的值赋给b。

4.重复步骤2和3，直到b等于0。此时，a即为最大公约数。

Format

Input

Output

Samples

60
36

12

57
81

3

121
33

11

Limitation

1s, 1024KiB for each test case.