Theo quan điểm của người Mazan những số đẹp là số có số lượng các ước của nó là số nguyên tố ví dụ: Số ~9~ có số lượng các ước là ~3~ gồm các ước ~(1, 3, 9)~ vì vậy số ~9~ là số đẹp. Bạn hãy giúp người Mazan tìm số lượng số đẹp trong đoạn từ ~1~ đến ~N~ cho trước.

• Dữ liệu vào: Số nguyên dương ~N (1 \le N \le 10^7)~.
• Kết quả: Một số duy nhất là số lượng số đẹp trong đoạn từ ~1~ đến ~N~.

Ví dụ:

Input

10

Output

6

Giải thích

Các số đẹp trong đoạn ~[1..10]~ gồm: ~2, 3, 4, 5, 7, 9~.

Ràng buộc:

• Có ~40\%~ số test ứng với ~1 \le N \le 10^3~;
• Có ~30\%~ số test ứng với ~10^3 \le N \le 5 \times 10^5~;
• Có ~30\%~ số test ứng với ~10^6 \le N \le 10^7~.