Số nguyên tố thuộc đoạn
Cho $Q$ truy vấn. Mỗi truy vấn, hãy trả lời câu hỏi: Có bao nhiêu số nguyên tố trong đoạn $[L,R]$.
Dữ liệu
- Dòng đầu tiên chứa số nguyên $Q \ (0 < Q \le 10^5)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L,R \ (1 \le L \le R \le 10^6)$.
Kết quả
- In trên $Q$ dòng, dòng thứ $i$ là kết quả cho truy vấn thứ $i$.
Ví dụ
Ví dụ 1
input
2
1 10
1 100
output
4
25
Comments