Ông X là lãnh đạo cấp cao của một tập đoàn đa quốc gia, ông có một tổ chuyên gia tư vấn gồm một số nhân viên. Mỗi nhân viên được gán cho một mã hiệu riêng biệt là một số nguyên dương ngẫu nhiên không lớn hơn \(n\ (n \leq 10^{6})\). Trong chuyến làm việc tại nước ngoài sắp tới, ông muốn chọn một số nhân viên đi cùng. Những nhân viên may mắn được chọn là những nhân viên có mã hiệu là các số “nguyên tố tương đương” (Các số nguyên tố tương đương là các số nguyên dương có chung tập ước nguyên tố, ví dụ: 15 và 75 là hai số nguyên tố tương đương).

Yêu cầu: Đưa ra số lượng nhân viên đi cùng lớn nhất có thể, biết các nhân viên được chọn đi lần này có mã hiệu nằm trong đoạn từ \(a\) đến \(b\ (1 \leq a \leq b \leq n \leq 10^{6})\)

Dữ liệu vào:

+ Ba số \(n,\ a,\ b\).

Kết quả:

+ Ghi một số duy nhất là kết quả bài toán

Ví dụ:

Ràng buộc:

+ 60% số test có \(1 \leq a \leq b \leq \ n \leq 100\).

+ 20% số test có \(1 \leq a \leq b \leq n \leq 1000\).

+ 20% số test không có thêm ràng buộc khác.