(primecount.*)

Một nhà toán học đang làm việc với các số nguyên tố cần sự giúp đỡ của bạn. Cụ thể, nhà toán học có \(t\) câu hỏi, mỗi câu hỏi là một cặp số \(l\) và \(r\), bạn cần trả lời số lượng số nguyên tố nằm trong đoạn \(\lbrack l,\ r\rbrack\), tính cả hai đầu. Nhận thấy các thí sinh tham gia Kỳ thi Olympic Truyền thống 30-4 có khả năng trả lời được câu hỏi này, nhà Toán học nhờ các bạn trợ giúp. Các bạn hãy giúp nhà Toán học nhé.

Yêu cầu: Hãy viết chương trình trả lời các truy vấn của nhà Toán học.

Dữ liệu vào:

+ Dòng đầu chứa số nguyên dương \(t\) \((1 \leq t \leq \ 1000)\) là số truy vấn.

+ \(t\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương, dòng thứ \(i\ + \ 1\) ghi cặp số \(l_{i},\ r_{i}\) \((1\ \leq \ l_{i} \leq \ r_{i} \leq \ 10^{9})\) là các tham số của truy vấn thứ \(i\).

+ Tổng độ dài của các đoạn truy vấn không vượt quá \(10^{6}\).

Kết quả: gồm \(t\) dòng, dòng thứ \(i\) chứa một số nguyên là câu trả lời của truy vấn thứ \(i\)

Ràng buộc: 50% số điểm của bài tương ứng với các test có \(L_{i},\ R_{i}\ \leq 10^{5}\) và tổng độ dài các đoạn truy vấn không vượt quá \(10^{5}\).

Ví dụ: