Bài 5: 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 \cdot 3 \cdot 5\), do đó \(30\) là "Mã số Tam Tài". \(50\) không phải là "Mã số Tam Tài" vì \(50 = 2 \cdot 5 \cdot 5\) (thừa số \(5\) xuất hiện \(2\) lần). \(24 = 2 \cdot 2 \cdot 2 \cdot 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]\).

Input

• 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 \cdot 10^6\)), giữa hai số có một dấu cách.

Output

• 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]\). Nếu không có số nào thì chỉ in ra số \(0\).

Example

20 52

2 30

1 105

7 30

1 20

0

Subtask

• 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 \cdot 10^6\).