J. Just an integer
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a directed graph $$$G = (V,E)$$$ with $$$n$$$ nodes. The set of vertices is $$$V = \{1,2,\dots,n\}$$$. For every node $$$u \in V$$$, there is a directed edge from $$$u$$$ to each of its proper divisors. Formally: $$$$$$ (u,v) \in E \quad \text{iff} \quad v \mid u \quad \text{and} \quad 1 \leq v \lt u. $$$$$$

For each node $$$u$$$, define:

  • $$$I(u)$$$: the length of the longest directed path in $$$G$$$ that ends at $$$u$$$.
  • $$$O(u)$$$: the length of the longest directed path in $$$G$$$ that starts at $$$u$$$.

The length of a path is the number of edges it contains.

Your task is to compute the following sum: $$$$$$ S(n) = \sum_{u=1}^{n} \max\big(I(u), O(u)\big). $$$$$$

Input

The input consists of a single integer $$$n$$$ ($$$1 \leq n \leq 10^{10}$$$).

Output

Output a single integer — the value of $$$S(n)$$$.

Examples
Input
1
Output
0
Input
3
Output
3
Input
4
Output
6
Input
5
Output
7