Bài 33.1. Thám Tử SNT và Cấp Độ Đặc Vụ - [Độ khó: Dễ]

Mô tả: Trong thế giới của các điệp viên, mỗi số nguyên tố được coi là một "Đặc Vụ SNT" có cấp độ riêng. Cấp độ của một Đặc Vụ SNT chính là vị trí của nó trong danh sách các số nguyên tố được sắp xếp tăng dần (ví dụ: 2 là Đặc Vụ cấp độ 1, 3 là Đặc Vụ cấp độ 2, 5 là Đặc Vụ cấp độ 3, v.v.). Cơ quan tình báo của bạn cần một công cụ để nhanh chóng xác định số lượng Đặc Vụ SNT có cấp độ nằm trong một khoảng cho trước để phân bổ nhiệm vụ. Bạn hãy viết chương trình giúp họ thực hiện công việc này.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên T (\(1 \le T \le 10^5\)), là số lượng truy vấn. T dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (\(1 \le L \le R \le 78498\)), là cấp độ thấp nhất và cao nhất của các Đặc Vụ SNT cần thống kê. Lưu ý: Đặc Vụ SNT cấp độ 78498 là số nguyên tố 999983.

OUTPUT FORMAT

Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng, là số lượng Đặc Vụ SNT có cấp độ từ L đến R (bao gồm cả L và R).

Ví dụ:

Input:

3
1 3
5 5
10 12

Output:

3
1
3

Giải thích:

• Các Đặc Vụ SNT và cấp độ tương ứng của chúng:
  • Cấp độ 1: 2
  • Cấp độ 2: 3
  • Cấp độ 3: 5
  • Cấp độ 4: 7
  • Cấp độ 5: 11
  • Cấp độ 6: 13
  • Cấp độ 7: 17
  • Cấp độ 8: 19
  • Cấp độ 9: 23
  • Cấp độ 10: 29
  • Cấp độ 11: 31
  • Cấp độ 12: 37
• Truy vấn 1 (1 3): Các Đặc Vụ cấp độ 1, 2, 3 là 2, 3, 5. Có tổng cộng 3 đặc vụ.
• Truy vấn 2 (5 5): Đặc Vụ cấp độ 5 là 11. Có tổng cộng 1 đặc vụ.
• Truy vấn 3 (10 12): Các Đặc Vụ cấp độ 10, 11, 12 là 29, 31, 37. Có tổng cộng 3 đặc vụ.