Đếm số nguyên tố trong đoạn lớn

Có \(k\) truy vấn, mỗi truy vấn cho hai số nguyên dương \(a \le b\). Với mỗi truy vấn, hãy đếm số các số nguyên tố trong đoạn \([a, b]\).

Input

• Dòng đầu chứa số nguyên \(k\).
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\).

Output

In ra \(k\) dòng, dòng thứ \(i\) là số lượng số nguyên tố trong đoạn của truy vấn thứ \(i\).

Constraints

• \(1 \le k \le 5\).
• \(1 \le a \le b \le 10^8\).

Sample Input

2
3 12
14 16

Sample Output

4
0

Explanation

Trong đoạn \([3, 12]\) có các số nguyên tố \(3, 5, 7, 11\). Đoạn \([14, 16]\) không có số nguyên tố nào.