Cho M truy vấn, mỗi truy vấn gồm 2 giá trị l_i, r_i (1 ≤ l_i ≤ r_i ≤ 10⁶).

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⁶)

- M dòng tiếp theo, mỗi dòng chứa hai số l_i và r_i.

OUTPUT: COUNTPRI.OUT

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