Sau khi thành công chống lại mã độc, CandySnowy liền nói: "Hay là mình đi chơi chút cho xả stress đi".
Vì vừa mới căng thẳng viết code, BabyOrange liền đồng ý. Trong chuyến đi, họ định đi tới công viên để chơi, ai dè họ lại bị đi lạc tới một "mê cung" kỳ quái, nói đúng hơn là một mạng lưới các trạm dịch chuyển.
Hệ thống dịch chuyển này gồm \(n\) trạm, giữa bất kỳ hai trạm phân biệt \(u\) và \(v\) nào cũng có một đường dẫn dịch chuyển. Tuy nhiên, việc di chuyển sẽ tiêu tốn một mức năng lượng được tính bằng công thức: \(w(u,v) = \frac{max(u,v)}{gcd(u,v)}\).
Trong đó, \(gcd(x,y)\) là ước chung lớn nhất của \(x\) và \(y\)
Hiện tại, hai người đang đứng ở trạm \(a\) và cửa thoát hiểm nằm ở trạm \(b\). Họ rất muốn ra nhưng vì đã dùng hết IQ để viết code nâng cấp nên giờ này không còn sức để giải nữa.
Hãy giúp BabyOrange và CandySnowy tìm đường từ \(a\) tới \(b\) mà tốn ít năng lượng nhất

Input

• Một dòng duy nhất chứa ba số \(n,a,b\) \((2 \le n \le 10^9, 1 \le a,b \le n, a \neq b)\)

Output

• Một số nguyên duy nhất biểu thị số năng lượng ít nhất để tới trạm \(b\)

Example

10 9 8

7

100 16 27

10

100 55 11

5