An là một người rất thích các con số, đặc biệt là những số may mắn. Theo quan niệm của An, một số nguyên dương được gọi là số may mắn nếu tổng các chữ số của nó là một số nguyên tố. Ví dụ, 124 là số may mắn vì là số nguyên tố, nhưng 123 không phải là số may mắn vì không phải là số nguyên tố.
Yêu cầu: Cho hai số nguyên dương và . Hãy đếm số lượng số may mắn trong đoạn .
Dữ liệu:
Dòng đầu tiên chứa số nguyên () là số lượng bộ test;
dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và ().
Kết quả:
Gồm dòng, mỗi dòng chứa một số nguyên là số lượng số may mắn trong đoạn tương ứng.
Ví dụ:Dữ liệu:
2
1 10
10 20
Kết quả:
4
5
Giải thích:
Trong đoạn có các số may mắn là 2, 3, 5, 7.
Trong đoạn có các số may mắn là 11, 12, 14, 16, 20.
Giới hạn:
Subtask #1 (40% số điểm): .
Subtask #2 (40% số điểm): và .
Subtask #3 (20% số điểm): Không có ràng buộc bổ sung.
