Shiba là một thanh niên đam mê tin học. Anh ta luôn tìm kiếm những thử thách mới để rèn luyện khả năng tính toán và tư duy logic của mình ~chủ yếu là để train đấm VOI~. Vào một ngày đẹp trời, khi đang tự học tại nhà, Shiba tình cờ đọc được một bài toán về các số nguyên tố và nhận ra rằng đó là một thử thách thú vị để giải quyết.

Bài toán yêu cầu Shiba đếm số lượng "số siêu đẹp" không lớn hơn một giá trị \(N\) cho trước. Một số nguyên dương \(K\) là "Số siêu đẹp" khi nó có dạng \(K = p \times q^3\) với \(p\) và \(q\) là hai số nguyên tố và \(p < q\). Shiba cảm thấy thích thú với bài toán này và quyết định bắt tay vào giải quyết nó.

Tuy nhiên sau bao lần nộp thì anh ấy vẫn không thể hoàn thành được bài này.

Biết rằng số nguyên tố là số nguyên dương chỉ chia hết cho \(1\) và chính nó, số nguyên tố đầu tiên là \(2\).

Yêu Cầu: Shiba cảm thấy bài trên quá khó, nên các bạn hãy giúp Shiba hoàn thành bài trên ~Để Shiba có động lực train để đấm VOI tiếp~.

Input

• Chứa một số nguyên dương \(N\) duy nhất (\(1 \le N \le 10^{18}\)).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(1 \le N \le 5000\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(5000< N \le 10^9\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

250

2