Cho số nguyên dương \(n\), hãy cho biết có bao nhiêu số trong đoạn \(\lbrack 1,n\rbrack\) có thể biểu diễn được dưới dạng \(a^{b}\) với \(a \geq 2;b \geq 2\).

Dữ liệu vào: Số nguyên \(n\) \((1 \leq n \leq 10^{10})\)

Kết quả: Một số nguyên cho biết kết quả bài toán

Ví dụ:

Input	Output
8	2

Ràng buộc:

+ Có 30% số test tương ứng 30% số điểm có \(n \leq 2000\)

+ Có 40% số test khác tương ứng 40% số điểm có \(n \leq 10^{5}\)

+ Có 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm