Số nguyên tố là một số tự nhiên chỉ gồm hai ước dương là 1 và chính nó.

Nhiệm vụ của bạn là: Hãy đếm số lượng số nguyên tố nằm trong phạm vi từ L đến R.

INPUT: PRIME.INP

• Dòng 1 chứa số q (1 ≤ q ≤ 10⁵) – số lượng truy vấn.
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (1 ≤ L ≤ R ≤ 10⁵)

OUTPUT: PRIME.OUT

• Gồm q dòng, mỗi dòng tương ứng là số lượng số nguyên tố thuột đoạn L đến R tương ứng với mô tả của đầu vào.

Ví dụ: