Написати програм који за дати природан број \(n\) исписује вредност Мертенсове функције \(M(n)\).

Мертенсова функција је дефинисана као \(M(n) = \sum_{i=1}^n \mu(i)\), где је \(\mu(i)\) Мебијусова функција:

\[\mu(i)= \left . \begin{cases} 0 & \text{ако је } i \text{ дељиво квадратом неког броја}\\ 1 & \text{ако је } i \text{ производ парног броја различитих простих бројева}\\ -1 & \text{ако је } i \text{ производ непарног броја различитих простих бројева}\\ \end{cases} \right . \]

Улаз

На стандардном улазу се налази природан број \(n\), не већи од милион.

Излаз

На стандардни излаз исписати један цео број, вредност поменуте функције.

Пример

Улаз

10

Излаз

-1

Објашњење

n       1   2   3   4   5   6   7   8   9  10
mi(n)   1  -1  −1   0  −1   1  −1   0   0   1
M(n)    1   0  −1  −1  −2  −1  −2  −2  −2  −1