Factor Solitaire

In the game of Factor Solitaire you start with the number $1$ and try to turn it into a given target number $n$ by repeatedly applying the following operation.

At each step, let $c$ be your current number. Choose two positive factors $a$ and $b$ with $c = a \cdot b$. Add $a$ to your current number, so $c$ becomes $c + a$. This step costs you $b$ points.

Repeat until your current number equals $n$. Your goal is to reach $n$ at the minimum possible total cost.

For example, one way to reach $15$ is:

• start with $1$;
• change $1$ to $1 + 1 = 2$ — cost so far $1$;
• change $2$ to $2 + 1 = 3$ — cost so far $1 + 2$;
• change $3$ to $3 + 3 = 6$ — cost so far $1 + 2 + 1$;
• change $6$ to $6 + 6 = 12$ — cost so far $1 + 2 + 1 + 1$;
• change $12$ to $12 + 3 = 15$ — done, total cost $1 + 2 + 1 + 1 + 4 = 9$.

In fact $9$ is the minimum possible total cost to reach $15$. Given a target number, compute this minimum total cost.

The input consists of a single integer $N$ with $1 \le N \le 5000000$. In at least half of the cases $N \le 50000$, in at least another quarter of the cases $N \le 500000$, and in the remaining cases $N \le 5000000$.

Print a single integer: the minimum total cost to reach $N$ starting from $1$.