Cho q câu hỏi, mỗi câu hỏi gồm hai số l và r. Với mỗi câu hỏi hãy đếm số lượng số nguyên tố trong đoạn [l, r].
Minh họa đếm số nguyên tố trong đoạn
Dữ liệu vào
Dòng đầu chứa số nguyên q. Mỗi dòng trong q dòng tiếp theo chứa hai số nguyên l và r.
Kết quả
q dòng, dòng thứ i là đáp án của câu hỏi thứ i.
Giới hạn
1 ≤ q ≤ 10^5; 1 ≤ l ≤ r ≤ 10^6.
Ví dụ 1 – vào
4 1 10 10 20 2 2 14 16
Ví dụ 1 – ra
4 4 1 0