Một số nguyên dương được gọi là có đúng ba ước số nguyên dương nếu nó chỉ có đúng ba ước phân biệt (tính cả 1 và chính nó).

Ví dụ: số \(4\) có ba ước là \(1, 2, 4\). Số \(9\) có ba ước là \(1, 3, 9\).

Yêu cầu: Cho hai số nguyên \(L\) và \(R\). Hãy đếm xem có bao nhiêu số trong đoạn \([L, R]\) có đúng ba ước số.

Dữ liệu vào

• Một dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le 10^{12}\), \(R - L \le 10^4\)).

Dữ liệu ra

• In ra một số nguyên duy nhất — số lượng số trong đoạn \([L, R]\) có đúng ba ước số.

Ví dụ

Gợi ý

Một số có đúng 3 ước khi và chỉ khi nó là bình phương của một số nguyên tố (\(p^2\)). Khi đó ba ước của nó là \(1, p, p^2\).

Do đó, bài toán trở thành: đếm số lượng số nguyên tố \(p\) sao cho \(p^2\) nằm trong đoạn \([L, R]\).