Số nguyên dương \(n\) được gọi là square-free nếu không có số nguyên tố \(p\) nào thỏa \(p^2 \mid n\). Cho \(N\), đếm số lượng số square-free trong \([1, N]\).

Định dạng đầu vào

• Một dòng chứa \(N\) (\(1 \le N \le 10^6\)).

Định dạng đầu ra

• Một số nguyên là số lượng số square-free.

Ví dụ

Input:

10

Output:

7

Ràng buộc

• 100% số điểm: \(N \le 10^6\).