인수 솔리테어

인수 솔리테어(Factor Solitaire) 게임에서는 수 $1$에서 시작하여, 다음 연산을 반복 적용해 주어진 목표 수 $n$으로 바꾸는 것이 목표입니다.

각 단계에서 현재 수를 $c$라고 하자. $c = a \cdot b$가 되도록 양의 인수 $a$와 $b$를 고른다. 그런 다음 현재 수에 $a$를 더하여 $c$를 $c + a$로 만든다. 이 단계의 비용은 $b$점이다.

현재 수가 $n$이 될 때까지 이 과정을 반복한다. 목표는 총 비용을 최소로 하여 $n$에 도달하는 것이다.

예를 들어 $15$에 도달하는 한 가지 방법은 다음과 같다.

• $1$에서 시작한다;
• $1$을 $1 + 1 = 2$로 바꾼다 — 지금까지의 비용 $1$;
• $2$를 $2 + 1 = 3$으로 바꾼다 — 지금까지의 비용 $1 + 2$;
• $3$을 $3 + 3 = 6$으로 바꾼다 — 지금까지의 비용 $1 + 2 + 1$;
• $6$을 $6 + 6 = 12$로 바꾼다 — 지금까지의 비용 $1 + 2 + 1 + 1$;
• $12$를 $12 + 3 = 15$로 바꾼다 — 완료, 총 비용 $1 + 2 + 1 + 1 + 4 = 9$.

실제로 $15$에 도달하는 최소 총 비용은 $9$이다. 목표 수가 주어질 때, 이 최소 총 비용을 구하여라.

입력은 정수 $N$ 하나로 이루어진다 ($1 \le N \le 5000000$). 전체 케이스 중 적어도 절반은 $N \le 50000$이고, 적어도 또 다른 4분의 1은 $N \le 500000$이며, 나머지는 $N \le 5000000$이다.

$1$에서 시작하여 $N$에 도달하는 최소 총 비용을 정수 하나로 출력한다.