Xây dựng hàm UCLN(a, b) để tìm ước số chung lớn nhất của hai số nguyên không âm a và b bằng thuật toán Euclid, sau đó áp dụng để tìm UCLN của hai số nhập từ bàn phím.

Thuật toán Euclid: UCLN(a, b) = UCLN(b, a % b), lặp cho đến khi b = 0 thì kết quả là a.

Input

Một dòng chứa hai số nguyên không âm \(a\), \(b\) (0 ≤ a, b ≤ 10^9), cách nhau bởi dấu cách.

Output

Một dòng duy nhất chứa ước chung lớn nhất của \(a\) và \(b\).

Sample Input

6 9

Sample Output

3

Subtask

• 30% (Nhỏ): 0 ≤ a, b ≤ 100
• 30% (Trung bình): 0 ≤ a, b ≤ 10^6
• 40% (Lớn): 0 ≤ a, b ≤ 10^9