전생했더니 슬라임 연구자였던 건에 대하여 (Easy)

안녕? 내 이름은 ntopia야.

나는 원래 지구에 살던 평범한 20대 청년이었어. 어느 날 길을 걷다가 괴한의 칼에 찔려 죽어버렸지. 그런데 정신을 차려보니 이세계에 떨어져 있는 거야. 여기에서 나는 슬라임만 파고드는 슬라임 연구자가 된 것 같아. 지금 아주 중요한 연구를 하고 있는데, 이 연구가 성공하면 원래 살던 세계로 돌아갈 수 있어. 이 연구를 도와주지 않을래?

이곳의 슬라임은 모두 슬라임 에너지를 갖고, 그 양은 $2$ 이상의 자연수로 나타나. 나는 슬라임을 분할했을 때 슬라임 에너지가 어떻게 변하는지를 연구하고 있어.

슬라임 분할은 한 마리를 쪼개서 두 마리를 만드는 방식이야. 에너지가 $K$인 슬라임을 적절히 분할하면 에너지가 $A$인 슬라임과 에너지가 $B$인 슬라임을 만들 수 있어. 이때 $A$와 $B$는 $2$ 이상의 자연수이고, 항상 $K = A \times B$를 만족해. 이렇게 계속 분할하다 보면 더 분할할 수 없는 슬라임도 나오겠지?

분할 기술이 아직 완벽하지 않아서 슬라임을 분할할 때마다 흠집이 하나씩 늘어나. 흠집이 $T$개인 슬라임을 분할하면 흠집이 $T + 1$개인 슬라임 두 마리가 생겨.

에너지가 $24$이고 흠집이 $1$개인 슬라임을 분할한 모습. 에너지가 $4$이고 흠집이 $2$개인 슬라임과 에너지가 $6$이고 흠집이 $2$개인 슬라임으로 나뉘었다.

나에게는 지금 슬라임 에너지가 $K$이고 흠집이 하나도 없는 슬라임이 있어. 이 슬라임을 분할하고 또 분할해서, 더 분할할 수 있는 슬라임이 남지 않을 때까지 전부 분할해야 해. 다 분할하고 나면 마지막에 남은 슬라임에 흠집이 어느 정도 생겨 있겠지. (물론 하나도 생기지 않을 수도 있어.) 그중에서 흠집이 가장 많은 녀석의 흠집 개수를 최소로 만드는 것이 내 연구 목표야.

내 연구를 도와줘! 부탁이야!

첫 줄에 처음 주어진 슬라임의 에너지 $K$ ($2 \le K \le 1\,000\,000$)가 주어진다.

슬라임을 끝까지 분할했을 때, 가장 많이 생긴 흠집 개수의 최솟값을 한 줄에 출력한다.

에너지가 $24$이고 흠집이 없는 슬라임에서 시작한다고 하자. 이 슬라임을 에너지가 $4$인 슬라임과 에너지가 $6$인 슬라임으로 분할하면 둘 다 흠집이 $1$개가 된다.

에너지가 $4$이고 흠집이 $1$개인 슬라임은 에너지가 $2$이고 흠집이 $2$개인 슬라임 두 마리로 분할된다.

에너지가 $6$이고 흠집이 $1$개인 슬라임은 에너지가 $2$이고 흠집이 $2$개인 슬라임과 에너지가 $3$이고 흠집이 $2$개인 슬라임으로 분할된다.

여기까지 분할하면 더 분할할 수 있는 슬라임이 남지 않는다. 이때 가장 많이 생긴 흠집 개수는 $2$개이고, 이보다 더 적게 만드는 분할 방법은 없다.