Công ty Đoàn gia đang hạn hẹp về ngân sách sau dịch bệnh COVID-19, nên chủ tịch Ban Đoàn ra một câu đố để lọc ra những nhân viên ưu tú nhất.

Câu đố như sau: Ban Đoàn cho các nhân viên của mình 1 giá trị nguyên dương n, yêu cầu các nhân viên của mình đếm số lượng số "Đoàn euro" trong khoảng từ 1 đến n. Những người đưa ra kết quả nhanh nhất sẽ được ở lại, còn lại sẽ nằm trong danh sách cắt giảm nhân sự

"Đoàn euro" là số mà tổng các ước của nó là số nguyên tố, VD: 2, 4, 16,... là "Đoàn euro". còn 1, 3, 10, ... thì không.

Input

Một dòng duy nhất là giá trị n.

Output

Một dòng duy nhất là số lượng "Đoàn euro" từ 1 đến n.

Constraints

• ~1 \le n \le 10 ^ 9~

Input Sample 1

10

Output Sample 1

3

Subtask

• Subtask 1 (30%): ~n \le 10 ^ 3~
• Subtask 2 (30%): ~n \le 10 ^ 5~
• Subtask 3 (40%): không có ràng buộc gì thêm