Cho M truy vấn, mỗi truy vấn gồm 2 giá trị li, ri (\(1 ≤ l_i ≤ r_i ≤ 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]\).

Dữ liệu vào

• Dòng 1 chứa M (\(1 ≤ M ≤ 10^6\))

• M dòng tiếp theo, mỗi dòng chứa hai số li và ri.

Kết quả

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

Ví dụ 1:

INPUT

   3
4 10
7 20
2 30

OUTPUT

2
5
10