Cho hai số nguyên dương \(L,R\).

Yêu cầu: Đếm số lượng các số nguyên tố trong phạm vi từ \(L\) đến \(R\).

Input

• Dòng đầu tiên chứa số nguyên \(T (1≤T≤10^4)\) là số bộ test.

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L,R(L≤R≤10^6 ).\)

Output

• Gồm \(T\) dòng, mỗi dòng ghi số lượng các số nguyên tố trong phạm vị từ \(L\) đến \(R\) ứng với test tương ứng.

Sample Input

2
1 7
3 19

Sample Output

4
16