Cho đinh nghĩa của hàm F(l,r) như sau:
F(l,r) = ∑x, ∀x, với x là số nguyên tố thuộc đoạn l và r.
Nói cách khác, F(l,r) là tổng tất cả các số nguyên tố thuộc đoạn l và r.
Cho các câu truy vấn, mỗi câu truy vấn gồm 2 số nguyên không âm l và r. Hãy tính F(l,r)
Input:
- Dòng đầu là số nguyên N thể hiện số truy vấn (1 ≤ N ≤ 500,000)
- Ứng với mỗi truy vấn là 2 số nguyên l và r (0 ≤ l ≤ r ≤ 106).
Output Format:
- In ra kết quả của mỗi truy vấn trên từng dòng.