Cho Q truy vấn. Mỗi truy vấn yêu cầu bạn đếm số lượng số nguyên tố nằm trong đoạn [L, R].

Input

Dòng đầu tiên chứa số nguyên Q — 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.

Output

Với mỗi truy vấn, in ra một số nguyên — số lượng số nguyên tố trong đoạn [L, R].

Ràng buộc

• ~1 ≤ Q ≤ 10^4~
• ~1 ≤ L, R ≤ 10^6~

Sample Input

9
3 17
1 11
2 18
1 15
4 15
4 18
4 17
2 12
4 20

Sample Output

6
5
7
6
4
5
5
5
6