Sau buổi học đầu tiên, các mentor thấy các bạn học sinh khá thích thú với kiến thức lập trình thú dị. Đặc biệt là trong việc nhập xuất và tính toán.

Ngay sau đó bạn Lộc K18 có đố bạn Tài K18 một bài toán rằng: cho một số nguyên dương n, hãy trả về số lượng các số từ 1 đến n mà không chia hết cho bất kì số trong tập hợp sau X = {2, 3, 5}.

Tài phải mất cả đêm để suy nghĩ để giải quyết bài toán này bằng kiến thức trong buổi học đầu tiên. Bạn có thể giúp Tài trả lời câu hỏi này thật sớm để yên tâm đi ngủ được không?

Input

Một dòng duy nhất chứa một số nguyên n.

Subtask 1 (50% số điểm): n ≤ ~10^8~

Subtask 2 (50% số điểm): n ≤ ~10^{18}~

Output

Một dòng duy nhất là kết quả của câu đố.

Examples

Input

7

Output

2  

*Note: * các số từ 1 đến 5 không chia hết cho {2, 3, 5} là {1, 7} nên kết quả là 2.