蜘蛛吃苍蝇

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

4052

 

这一招是《成龙历险记》中的阿福众多招式中的一种,但不幸的是阿福真的吃到了苍蝇。这只苍蝇最初重量为 $n$,在阿福肚子中的苍蝇每过一分钟为会缩小为能整除 $n$ 的数,缩小到 $1$ 为止,且这些数是递减的。不过这不是普通的苍蝇,这是一只带有魔法的苍蝇,每当苍蝇改变一次重量或者苍蝇被阿福吃进去时,阿福每次可以获得 $\mu(i)$ 点能量(此处的 $i$ 为 $n$ 的因子),比如 $n=12$ 时:

苍蝇重量的变化过程:$12→6→4→3→2→1$

阿福可获得的能量为:
$\mu(12)+\mu(6)+\mu(4)+\mu(3)+\mu(2)+\mu(1)=0+1+0+(-1)+(-1)+1=0$

$\mu$ 为莫比乌斯函数,它的定义如下:

$$\mu(n)=\begin {cases}1&n=1 \\ (-1)^{k}&n=p_1\times p_2... \\ 0& others \end{cases}$$

当 $n$ 等于 $1$ 时 $\mu(1)=1$;当 $n$ 为不同素数相乘得到的 $\mu(n)=(-1)^{k}$,这里的 $k$ 为素数个数,例如:$\mu(6)=1$,$\mu(2)=-1$,因为 $6=2\cdot3$,$2=2$。其他情况均为 $0$,例如:$\mu(12)=0$,因为 $12=2\cdot2\cdot3$,$2$ 出现了两次。

现在已知苍蝇重量,请你求出阿福可获得的能量为多少。

Input

输入一个整数 $n$ $(1 \leqslant n \leqslant 9\cdot10^{18})$,代表苍蝇的重量。

Output

输出一个整数代表阿福所获得的能量。

Sample Input

1

Sample Output

1

Hint

Source

【2016级ACM暑假集训 结训赛(数据结构组)】MLE_kenan