Background

很久以前的数学家发现了一个找“最大公因数”的好办法：辗转相除法。 它天生就是一个递归——大问题里藏着一个一模一样的小问题。

Description

给定两个正整数 $a$ 和 $b$，请用递归求出它们的最大公因数 $\gcd(a,b)$。

辗转相除法的递归写法非常短：

$$\gcd(a, b) = \begin{cases} a, & b = 0 \\ \gcd(b,\ a \bmod b), & b \ne 0 \end{cases}$$

其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

Format

Input

一行两个整数 $a$ 和 $b$（$1 \le a, b \le 10^9$），中间用一个空格隔开。

Output

一行一个整数，表示 $a$ 和 $b$ 的最大公因数。

Samples

12 18

6

Hint

每做一次取余，数字都会变小，所以一定会停下来——这正是递归“问题越来越小”的特点。

Limitation

1s, 256MiB for each test case.