Killable Hilichurls

In this problem, Hilichurls are numbered from 1 to n. A Hilichurl is considered killable if and only if there exists a perfect square number, greater than \(1\), that divides its number. For example, the Hilichurl numbered 12 is killable because \(4\) (which is \(2^2\)) divides 12, while the Hilichurl numbered 15 is not killable.

Your task is to compute the number of killable Hilichurls among those numbered from \(1\) to \(n\). Since Zhongli believes in "good enough," your answer is allowed to have an absolute error of at most \(2 \times 10^4\) compared to the exact answer.

Note: A number is killable if it is divisible by any perfect square greater than 1. Equivalently, these are the numbers that are not square-free.

The exact count of killable Hilichurls is \(n-\text{squarefree}(n)\), where the number of square-free numbers up to \(n\) can be computed via the formula:

\[ \text{squarefree}(n) = \sum_{d=1}^{\lfloor\sqrt{n}\rfloor} \mu(d) \left\lfloor \frac{n}{d^2} \right\rfloor, \]

with \(\mu(d)\) being the Möbius function. You may use this exact method or any method that yields an answer with an absolute error no more than \(2\times10^4\).

inputFormat

The input consists of a single line containing an integer \(n\) \((1 \leq n \leq 10^{12})\), denoting the number of Hilichurls.

outputFormat

Output a single integer representing the count of killable Hilichurls among those numbered from \(1\) to \(n\). Your answer may have an absolute error of at most \(2 \times 10^4\).

sample

12

3