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.

INPUT

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~.

OUTPUT

Gồm ~T~ dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

SAMPLE INPUT

2
2 7
1 100

SAMPLE OUTPUT

5
32

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ố.

SUBTASKS

• 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 \%~ số điểm tương ứng với số test có ~1 \le a \le b \le 10^6~ và ~T \le 10^5~.