Để đến được thử thách tiếp theo, em phải điều khiển C-Bot di chuyển trong vũ trụ ảo, tìm đến vị trí một cánh cổng thời gian.

Biết rằng các cổng thời gian được đánh số theo thứ tự là các số hạng của dãy số \((u_n)\) theo quy tắc sau: \(u_1 = \frac{1}{1}\). Với mỗi số hạng \(u_k = \frac{a}{b}\) đã có trong dãy (bắt đầu từ \(k = 1\)), ta lần lượt thêm vào cuối dãy hai số hạng mới là \(\frac{a}{a+b}\) và \(\frac{a+b}{b}\) (\(a, b\) nguyên dương).

Ví dụ:

• Với \(u_1 = \frac{1}{1}\), ta thêm \(\frac{1}{2}\) và \(\frac{2}{1}\).
• Với \(u_2 = \frac{1}{2}\), ta thêm \(\frac{1}{3}\) và \(\frac{3}{2}\).
• Với \(u_3 = \frac{2}{1}\), ta thêm \(\frac{2}{3}\) và \(\frac{3}{1}\).

Cứ tiếp tục như vậy, ta thu được dãy: \(\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \dots\)

Yêu cầu: Cho phân số \(\frac{p}{q}\). Hãy tìm số nguyên dương \(n\) sao cho \(u_n = \frac{p}{q}\).

Input

• Một dòng duy nhất chứa hai số nguyên dương \(p\) và \(q\) cách nhau bởi ký tự / (dữ liệu đảm bảo \(\frac{p}{q}\) là phân số tối giản và \(p, q\) nguyên dương).

Output

• Một số nguyên dương \(n\) duy nhất tìm được.

Example

1/3

4

5/2

11

Scoring

• Dữ liệu đảm bảo \(n \le 2^{31} - 1\).
• Có \(50\%\) số test có \(n \le 10^6\).