Problem Description

For a positive integer $ n $, let $ f(n) $ be the number of prime factors of $ n $ counted with multiplicity. For example, since $200 = 2^3 \times 5^2$, we have $ f(200) = 5 $.

Given a positive integer $ N $, find $\sum_{n=1}^N (-1)^{f(n)}$.

Input Format

$ N $

Output Format

Output the value of $\sum_{n=1}^N (-1)^{f(n)}$ in one line.

Sample Input and Output

Sample Input #1

6

Sample Output #1

0

Sample Input #2

2019

Sample Output #2

-25

Sample Input #3

906150257

Sample Output #3

1

Notes/Hints

Constraints

• $1 \le N \le 10^{11}$.

Partial Points

• If you solve the dataset satisfying $N \le 10^{10}$, you will be awarded 45 points.
• If you solve the dataset without additional constraints, you will be awarded an additional 55 points.

Sample Explanation 1

Since $ f(1) = 0 $, $ f(2) = 1 $, $ f(3) = 1 $, $ f(4) = 2 $, $ f(5) = 1 $, $ f(6) = 2 $, the answer is $ (-1)^0 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^1 + (-1)^2 = 0 $.

见题面 Input 部分

见题面 Output 部分