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].

INPUT: COUNTPRI.INP

• 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.

Ví dụ: