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 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~ thỏa mãn ~a ≤ x ≤ b~.

Dữ liệu:

• Dòng đầu là số nguyên dương ~M~ (~1 ≤ M ≤ 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 ≤ a ≤ b ≤ 10^6~).

Kết quả:

Ghi ra ~M~ dòng, mỗi dòng là kết quả tương ứng tìm được.

Ví dụ:

SNUM.INP

2
1 10
1 100

SNUM.OUT

2
4

Giải thích:

• Từ số 1 đến số 10 có 2 số đặc biệt là 4, 9.
• Từ số 1 đến số 100 có 4 số đặc biệt là 4, 9, 25, 49.

Ràng buộc:

• Có 20% số điểm ứng với (~1 ≤ M ≤ 10^2; 1 ≤ b ≤ 10^2~);
• Có 30% số điểm ứng với (~1 ≤ M ≤ 10^3; 1 ≤ b ≤ 10^3~);
• 50% số điểm còn lại không có giới hạn gì thêm.

Nguồn