Một bác thợ mộc muốn làm một chiếc kệ để đồ từ hai tấm gỗ có chiều dài lần lượt là ~a~ và ~b~ (cùng đơn vị độ dài). Bác thợ muốn cắt hai tấm gỗ này thành các thanh gỗ có cùng độ dài mà không để thừa mẩu gỗ nào.

Yêu cầu: Hãy cho biết độ dài lớn nhất có thể của mỗi thanh gỗ được cắt sao cho không để thừa mẩu gỗ nào sau khi cắt.

Input

Hai số nguyên dương ~a~ và ~b~ (~1 \le a, b \le 10^{15}~).

Output

Một số nguyên là độ dài lớn nhất có thể của mỗi thanh gỗ được cắt.

Sample Input

18 30

Sample Output

6

Subtasks

• Có ~80\%~ số test tương ứng ~80\%~ số điểm có ~1 \le a, b \le 10^6~.
• Có ~20\%~ số test tương ứng ~20\%~ số điểm có ~10^6 < a, b \le 10^{15}~.