Nguyên tố đẹp

Số nguyên tố là số tự nhiên lớn hơn \(1\) và có hai ước là \(1\) và chính nó. Một số nguyên tố được gọi là số nguyên tố "đẹp" khi nó không chứa chữ số \(3\), \(5\) và \(7\). Ví dụ các số \(2\), \(11\), \(19\) là các số nguyên tố "đẹp", các số \(3, 5, 7, 73, 37\) không phải là số nguyên tố "đẹp".

Cho số nguyên dương \(N\) \((1 \leq N \leq 10^5)\).

Yêu cầu: Đếm tất cả các số nguyên tố "đẹp" có trong đoạn từ \(1\) đến \(N\).

Input

Dữ liệu vào: Từ tệp nguyentodep.inp chứa duy nhất số nguyên dương \(N\).

Output

Dữ liệu ra: Ghi ra tệp nguyentodep.out chứa số nguyên dương duy nhất là số lượng số nguyên tố "đẹp".

Example

20

3

Scoring

• \(70\%\) số test tương ứng \(70\%\) số điểm với \(1 \leq N \leq 10^4\).
• \(30\%\) số test tương ứng \(30\%\) số điểm với \(1 \leq N \leq 10^5\).