Mã số Phố Hiến

Vào thế kỷ XVII, Phố Hiến (Hưng Yên) là thương cảng sầm uất bậc nhất Đàng Ngoài, nơi tàu thuyền từ Nhật Bản, Hà Lan, Anh, Pháp, ... tấp nập vào ra buôn bán.

Để quản lý hàng vạn kiện hàng tơ lụa và gốm sứ xuất khẩu, người ta đánh mã số cho các lô hàng. Các thương nhân ở đây đặc biệt ưa thích những kiện hàng có mã số đặc biệt gọi là “Mã số Tam Tài”. Theo quan niệm của các thương nhân lúc bấy giờ, mã số đó là số may mắn vì nó tượng trưng cho “Thiên - Địa - Nhân”.

Một mã số kiện hàng được coi là “Mã số Tam Tài” nếu giá trị của nó là tích của đúng 3 số nguyên tố khác nhau. Ví dụ: $30 = 2 \times 3 \times 5$, do đó 30 là “Mã số Tam Tài”. 50 không phải là “Mã số Tam Tài” vì $50 = 2 \times 5 \times 5$ (thừa số 5 xuất hiện 2 lần). $24 = 2 \times 2 \times 2 \times 3$ nên 24 cũng không phải.

Yêu cầu: Cho hai số nguyên dương L và R. Hãy đếm xem trong đoạn [L, R] có bao nhiêu số là “Mã số Tam Tài” và xác định “Mã số Tam Tài” đầu tiên có trong đoạn [L, R].

Dữ liệu vào từ tệp MASO.INP: Một dòng duy nhất chứa hai số nguyên dương L và R $(1 \le L \le R \le 10^{12}$ và $R - L \le 2 \times 10^6)$, giữa hai số có một dấu cách.

Kết quả ghi ra tệp MASO.OUT: Một dòng duy nhất gồm hai số tương ứng là số lượng “Mã số Tam Tài” trong đoạn [L, R] và “Mã số Tam Tài” đầu tiên có trong đoạn [L, R].

• Subtask 1 (30% số điểm): $1 \le L \le R \le 10^4$.
• Subtask 2 (25% số điểm): $R \le 10^{12}$, nhưng $R - L \le 1000$.
• Subtask 3 (30% số điểm): $R \le 10^{12}$ và $R - L \le 10^6$.
• Subtask 4 (15% số điểm): $R \le 10^{14}$ và $R - L \le 2 \times 10^6$.