Hôm nay Hiếu được học về chủ đề số nguyên tố. Hiếu 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ố.

Hiếu 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à 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: Nhập từ bàn phí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ả: In đáp án ra màn hình 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ụ:

Input 1

2
2 7
1 100

Output 1

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 $\le$ a $\le$ b $\le$ 200 và T $\le$ ${10}^2$;
• Có 30% số điểm tương ứng với số test có 1 $\le$ a $\le$ b $\le$ 2000 và T $\le$ ${10}^3$;
• Có 30% còn lại tương ứng với số test có 1 $\le$ a $\le$ b $\le$ ${10}^6$ và T $\le$ ${10}^5$.