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