問題文

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

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

制約

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

部分点

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

入力例 1

6

出力例 1

7

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

入力例 2

2019

出力例 2

6028

入力例 3

906150257

出力例 3

3660251364