Cho hai số \(a, b\). Ta cần biến đổi để một trong hai số \(a\) hoặc \(b\) về \(0\).

Ở mỗi phép biến đổi, ta thực hiện như sau:

• Nếu \(a \ge b\), ta đặt lại \(a\) bằng \(a-b\)
• Ngược lại, ta đặt lại \(b\) bằng \(b-a\).

Đếm số lượng phép biến đổi cần phải thực hiện.

Input

• Một dòng duy nhất chứa hai số \(a, b\) (\(a, b \le 10^{18}\)).

Output

• Một dòng duy nhất chứa số lượng phép biến đổi cần thực hiện.

Subtask

• Subtask \(1\) (\(40\%\) số điểm): \(a, b \le 10^6\)
• Subtask \(2\) (\(20\%\) số điểm): \(a\) chia hết cho \(b\)
• Subtask \(3\) (\(40\%\) số điểm): \(a, b \le 10^{18}\)

Sample

12 18

3