Bạn Nguyên rất yêu thích môn Toán. Trong lúc giải các bài toán về số học, bạn ấy phát hiện ra các số mà mình tìm được có nhiều số đặc biệt với đặc điểm là chỉ có 3 ước số nguyên dương khác nhau. Bạn Nguyên đặt tên cho các số này là số T-Nguyên tố.

Yêu cầu: hãy lập trình giúp bạn Nguyên đếm xem có bao nhiêu số T-Nguyên Tố có giá trị không vượt quá số nguyên dương \(N\) cho trước

Input

• Một dòng chứa số nguyên dương \(N\ (2 \le N \le 10^9)\).

Output

• Ghi ra số lượng số T-Nguyên tố tìm được.

Example

6

1

Scoring

• 80% số test với \(1 \le N \le 10^6\)
• 20% số test với \(10^6 < N \le 10^9\)