Một ngày, khi học sinh lớp 1 đang học về số học, giáo sư Wu Zi Mu đã ra bài tập như sau: “Định nghĩa F(N) là số ước nguyên dương của N. Ví dụ: F(12)=6,F(5)=2. Cho Q truy vấn, mỗi truy vấn chứa hai số A,B. Nhiệm vụ là đếm tất cả số X nằm trong khoảng [A,B] mà F(X) là số nguyên tố lớn hơn 2.” Học sinh lớp 1 đang cố tìm cách để giải bài này, nhưng không tìm ra được. Các bạn hãy giúp cho các học sinh đó nhé. Dữ liệu vào: Gồm Q+1 dòng: Dòng đầu tiên chứa số Q là số truy vấn Q dòng tiếp theo, dòng thứ i chứa hai số Ai, Bi là truy vấn thứ i. Kết quả: Gồm Q dòng là kết quả của Q truy vấn trên. Ví dụ: Input: 2 3 25 1 100 Output: 4 7 Giới hạn: 30% số test đầu tiên có 1≤A≤B≤10^3,Q≤10^3 30% số test tiếp theo có 1≤A≤B≤10^6,Q≤10^5 40% số test còn lại có 1≤A≤B≤10^12,Q≤10^5 Thời gian chạy: 0.4s = 400ms