問題文

正の整数 n に対し，f(n) を n が持つ素因数を重複を込めて数えた個数とする．例えば，200 = 2^3 \times 5^2 なので，f(200) = 5 となる．

正の整数 N が与えられるので，\sum_{n=1}^N (-1)^{f(n)} を求めよ．

制約

• 1 \le N \le 10^{11}．

部分点

• N \le 10^{10} を満たすデータセットに正解した場合は，45 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 55 点が与えられる．

入力例 1

6

出力例 1

0

f(1) = 0，f(2) = 1，f(3) = 1，f(4) = 2，f(5) = 1，f(6) = 2 なので，答えは (-1)^0 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^1 + (-1)^2 = 0 である．

入力例 2

2019

出力例 2

-25

入力例 3

906150257

出力例 3

1