Cho một số nguyên dương ~n~ (~1 \le n \le 10^9~).

Đếm các số nguyên trong đoạn ~[1, n]~ mà có tổng các ước nguyên dương là số nguyên tố.

Dữ liệu

Một số nguyên dương duy nhất ~n~.

Kết quả

Một số nguyên duy nhất là số các số nguyên trong đoạn ~[1, n]~ mà có tổng các ước là số nguyên tố.

Ví dụ

PRIM.INP

10

PRIM.OUT

3

Giới hạn

• Subtask 1 (30% số điểm): ~n \le 10^3~;
• Subtask 2 (30% số điểm): ~n \le 10^5~;
• Subtask 3 (20% số điểm): ~n \le 10^8~;
• Subtask 4 (20% số điểm): không có thêm ràng buộc nào.