F. Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Little Y came cross a function that confused her a lot.

$$$$$$ f(n) = \begin{cases} 1, & n \in \{1\} \bigcup \operatorname{Prime} \\ p\,f(p^{k-2}), & n = p^k ~ (p \in \operatorname{Prime}; ~ k > 1) \\ f(p_1^{e_1})\prod_{i=2}^r {p_i}^{e_i}, & n = \prod_{i=1}^r {p_i} ^ {e_i} ~ (p_1 < p_2 < \cdots < p_r; ~ p_i \in \operatorname{Prime}; ~ r \ge 2) \end{cases} $$$$$$

Now Little Y is interested in $$$\sum_{i=1}^n f(i)$$$. Can you help her?

Input

One line contains one integer denoting $$$n ~ (1 \le n \le {10}^{7})$$$.

Output

One line, the number denoting the answer.

Examples
Input
10
Output
20
Input
100
Output
1487
Note

For the first sample, $$$f(1) = 1$$$, $$$f(2) = 1$$$, $$$f(3) = 1$$$, $$$f(4) = 2$$$, $$$f(5) = 1$$$, $$$f(6) = 3$$$, $$$f(7) = 1$$$, $$$f(8) = 2$$$, $$$f(9) = 3$$$, $$$f(10) = 5$$$.

It is guaranteed that the answer will always be less than $$$2^{64}-1$$$.

Little Y wonders whether you can solve $$$n$$$ up to $$${10}^{10}$$$.