Cho hai số nguyên dương $L,R (L≤R≤10^6).$

Yêu cầu: Đếm số lượng các số trong đoạn $[L,R]$ sao cho số lượng ước dương của số đó là một số nguyên tố.

Input:

Dòng đầu tiên chứa số nguyên $T$ là số bộ test, với mỗi bộ test gồm:

• Gồm một dòng chứa 2 số $L,R (L≤R≤10^6 ).$

Output:

• Gồm $T$ dòng, mỗi dòng tương ứng với kết quả của dữ liệu vào.

Ràng buộc:

• Subtask 1: 40% test có $1≤L≤R≤200;T≤10^2;$

• Subtask 2: 30% test có $1≤L≤R≤2000;T≤10^3;$

• Subtask 3: 30% test có $1≤L≤R≤10^6;T≤10^5;$

Sample Input

2
2 7
1 100

Sample Output

5
32