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.

Example

18 30

6

Scoring

• 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}\).