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.

Input

• Số nguyên dương \(N\) \((1 \le N \le 10^7)\).

Output

• Một số duy nhất là số lượng số đẹp trong đoạn từ \(1\) đến \(N\).

Example

10

6

Scoring

• Có \(40\%\) số test/điểm ứng với \(1 \le N \le 10^3\).
• Có \(30\%\) số test/điểm ứng với \(10^3 \le N \le 5 \times 10^5\).
• Có \(30\%\) số test/điểm ứng với \(10^6 \le N \le 10^7\).