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 [a, b] 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:

Tệp văn bản CAU2.INP gồm:

• 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ả:

Tệp văn bản CAU2.OUT gồm T dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Ví dụ:

CAU2.INP

2

2 7

1 100

CAU2.OUT

5

32

Giải thích

Trong đoạn [2, 7] có 5 số thỏa mãn là 2, 3, 4, 5, 7 (vì 2, 3, 5, 7 có 2 ước dương; 4 có 3 ước dương; mà 2 và 3 đều là số nguyên tố). Số 6 không thỏa mãn vì 6 có 4 ước dương mà 4 không phải số nguyên tố. …

Ràng buộc:

• Có 40% số điểm tương ứng với số test có 1 ≤ a ≤ b ≤ 200 và T ≤10^2;
• Có 30% số điểm tương ứng với số test có 1 ≤ a ≤ b ≤ 2000 và T ≤10^3;
• Có 30% còn lại tương ứng với số test có 1 ≤ a ≤ b ≤ 106 và T ≤ 10^5.