Bài 10: Bí ẩn 3 ước số

Yêu cầu: Cho ~Q~ truy vấn. Mỗi truy vấn gồm hai số nguyên dương ~L, R~. Hãy đếm xem trong đoạn từ ~L~ đến ~R~ có bao nhiêu số nguyên dương có đúng 3 ước số.

Giới hạn:

• ~1 \le Q \le 10^5~
• ~1 \le L \le R \le 10^{12}~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Dữ liệu vào (Input):

• Dòng đầu tiên là số lượng truy vấn ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~.

Dữ liệu ra (Output):

• In ra ~Q~ dòng, mỗi dòng là số lượng số có đúng 3 ước nằm trong đoạn ~[L, R]~.

Ví dụ: Input:

1
1 10

Output:

2

(Giải thích: Từ ~1~ đến ~10~ có đúng 2 số có 3 ước là ~4~ (các ước: ~1, 2, 4~) và ~9~ (các ước: ~1, 3, 9~).)