Hôm nay cô giáo dạy An về số nguyên tố. Số nguyên tố là số tự nhiên lớn hơn 1, không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số là 1 và chính nó. Các số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Để kiểm tra xem An có hiểu bài không, cô tổ chức 1 trò chơi nhỏ. Cô sẽ hỏi T câu hỏi, với mỗi câu hỏi có cho 2 số L, R và yêu cầu An xác định xem trong đoạn [L,R] có bao nhiêu số nguyên tố.

Yêu cầu:

• Với mỗi câu hỏi bạn hãy thay An đếm xem có bao nhiêu số nguyên tố thuộc đoạn [L, R].

Dữ liệu đọc từ tệp DemNT.Inp gồm:

• Dòng đầu ghi số nguyên dương T (0<T≤10⁶)</li>
• T dòng tiếp theo, mỗi dòng chứa hai số L và R (1≤L≤R≤10⁶)

Kết quả:

• In ra số lượng số nguyên tố trong đoạn [L, R] (mỗi số ghi trên 1 dòng)

Ví dụ:

Giới hạn:

• Có 60% test ứng với T ≤ 10⁴
• Có 40% test ứng với 10⁴ < T ≤ 10⁶