DP - Đếm số lượng nguyên tố

Cho \(M\) truy vấn, mỗi truy vấn gồm 2 giá trị \(l_i, r_i\) \((1 \le l_i \le r_i \le 10^6)\). Với mỗi truy vấn bạn phải trả lời câu hỏi: có bao nhiêu số nguyên tố thuộc đoạn \([l_i,r_i]\).

Input

• Dòng 1 chứa \(M\) \((1 \le M \le 10^6)\)
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số \(l_i\) và \(r_i\).

Output

• Mỗi dòng chứa 1 câu trả lời tương ứng với truy vấn trong input.

Example

3
4 10
7 20
2 30

2
5
10