Một số nguyên dương được gọi là số “đặc biệt” nếu số đó có đúng 3 ước nguyên dương đôi một dương khác nhau.

Yêu cầu: Cho \(m\) cặp số nguyên dương \((a;b)\), hãy đếm số lượng số “đặc biệt” \(x\) thoả mãn \(a \leq \ x \leq b\).

Dữ liệu:

• Dòng đầu là số nguyên dương \(m\ (1\ \leq \ m\ \leq \ 10^{5})\).

• M dòng tiếp theo mỗi dòng chứa hai số nguyên dương \(a,\ b\) cách nhau bởi một khoảng trắng \((1 \leq a \leq b \leq 10^{6})\).

Kết quả:

• Ghi \(m\) dòng, mỗi dòng là kết quả tương ứng tìm được.

Ví dụ:

Ràng buộc:

• Có 20% số điểm ứng với \((1 \leq m \leq 10^{2};\ 1 \leq b \leq 10^{2})\)

• Có 30% số điểm ứng với \((1 \leq m \leq \ 10^{3};\ 1 \leq b \leq 10^{3})\)

• 50% số điểm còn lại không có ràng buộc gì thêm.