(ts10ls2425c2.*)

Hôm nay Lam được học về chủ đề số nguyên tố. Lam biết số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước là 1 và chính nó.

Ví dụ: 2, 3, 5, … là các số nguyên tố; các số 4, 6, 8, … không phải số nguyên tố.

Lam nghĩ ra một bài toán để đố các bạn trong lớp như sau: Cho hai số nguyên dương a và b. Hãy đếm trong đoạn \(\lbrack a,\ b\rbrack\) có bao nhiêu số mà số lượng các ước dương của nó là một số nguyên tố.

Yêu cầu: Các bạn hãy viết chương trình giải bài toán trên.

Dữ liệu vào:

+ Dòng 1: chứa số nguyên dương \(T\) là số lượng các đoạn cần đếm;

+ \(T\) dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương a và b.

Kết quả:

+ Ghi \(T\) dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Ví dụ:

Ràng buộc:

• Có 40% số điểm tương ứng với số test có \(1\ \leq \ a\ \leq \ b\ \leq \ 200\) và \(T\ \leq 10^{2}\);

• Có 30% số điểm tương ứng với số test có \(1\ \leq \ a\ \leq \ b\ \leq \ 2000\) và \(T\ \leq 10^{3}\);

• Có 30% còn lại tương ứng với số test có \(1\ \leq \ a\ \leq \ b\ \leq \ 10^{6}\) và \(T\ \leq \ 10^{5}\).