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

Yêu cầu: Với mỗi truy vấn, hãy đếm số lượng số nguyên tố trong đoạn ~[L, R]~.

Input

• Dòng 1 chứa số ~q~ (~1 \le q \le 10^5~) – 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 \le L \le R \le 10^5~).

Output

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

Sample Input 1

1
1 10

Sample Output 1

4