Số nguyên dương \(n\) được gọi là "square-free" (không có ước chính phương) 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 đoạn \([1, N]\).

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

• Một dòng chứa số nguyên \(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

Giải thích: Các số square-free: 1, 2, 3, 5, 6, 7, 10 (7 số). Các số không square-free: 4, 8, 9.

Ràng buộc

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