Giữa mùa hè nóng nực như đứng gần Mặt Trời, ledinhbaonam và uia quyết định đi đến Bà Nà Hills để hóng cái lạnh. Vì sự chênh lệch nhiệt độ giữa hai nơi, uia muốn tạo ra 1 loại số là số nóng. Nhưng ledinhbaonam muốn tạo ra thêm 1 loại số gọi là số lạnh.

• Số nóng được định nghĩa là một số nguyên tố và tổng các chữ số của nó là 1 số chẵn.
• Số lạnh được định nghĩa là một số nguyên tố có khoảng cách đến 1 số chính phương gần nó nhất không vượt quá 7 đơn vị.

Tuy vậy, PhuocThien muốn gộp hai số lại vì không muốn một cuộc chiến diễn ra. Anh quyết định tạo ra số nóng lạnh. Nó được định nghĩa như sau:

• Là một số nguyên tố.
• Tổng các chữ số của nó là một số chẵn.
• Số đó có khoảng cách đến 1 số chính phương gần nó nhất không vượt quá 7 đơn vị.

Vì bản tính ghét các số 8 vì nó không làm gì cả. ledinhbaonam và uia ra thêm 1 điều kiện như sau:

• Số nóng lạnh là 1 số không được tồn tại số 8.

ledinhbaonam và uia thách Prototype tìm được số lượng số nóng lạnh nhỏ hơn một số \(N\) cho trước.
Các bạn coders hãy giúp Prototype giải được bài toán này nhé!

Input

• 1 dòng đưa ra số nguyên dương \(N\) (\(100 \le N \le 10^{12}\))

Output

• 1 dòng đưa ra số lượng số nóng lạnh nhỏ hơn hoặc bằng \(N\)

Example

100

12

5000

71