Cho hai số nguyên dương \(L\) ≤ \(R\). Hãy đếm xem trong đoạn \([L, R]\) có bao nhiêu số nguyên tố.

Input:

• Dòng đầu ghi số nguyên dương \(T\) là số bộ test. (\(T\) <= \(10^5\))
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\) cách nhau bởi một dấu cách. \((1 < L \le R \le 10^8)\)

Output:

• Với mỗi cặp số \(L\) và \(R\), ghi ra trên một dòng số số nguyên tố trong đoạn \([L, R]\). (Đoạn \([L, R]\) ít hơn \(10^8\) phần tử)

Example:

Input1:

2
2 3
10 15

Output1:

2
2

Input2:

3
10 12
5 10
7 25

Output2:

1
2
6