Nguyên tố

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, \dots\) là các số nguyên tố; các số \(4, 6, 8, \dots\) 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.

Input

• Dòng đầu chứa số nguyên dương \(T\) (\(T \le 10^5\)) 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\) (\(1 \le a \le b \le 10^6\)).

Output

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

Notes

Trong đoạn \([2, 7]\) có \(5\) số thỏa mãn là \(2, 3, 4, 5, 7\).

Trong đó:

• \(2, 3, 5, 7\) có \(2\) ước dương;

• \(4\) có \(3\) ước dương.

Cả \(2\) và \(3\) đều là số nguyên tố.

Scoring

• (\(40\%\)) \(1 \le a \le b \le 200\) và \(T \le 10^2\);

• (\(30\%\)) \(1 \le a \le b \le 2000\) và \(T \le 10^3\);

• (\(30\%\)) \(1 \le a \le b \le 10^6\) và \(T \le 10^5\).