곱셈 분리 게임은 다음과 같다. 숫자 1부터 시작해서 다음의 연산을 통해 주어진 수 N에 도달해야 한다.

<연산 과정>-------------------------------------------------------------------------------

매 단계에서 현재의 수가 c라면 이것을 2개의 정수 a, b로 분리하고(c=a*b) 현재의 수 c에 a를 더한다. 이때 발생하는 비용은 b다. 이러한 과정을 현재의 수가 주어진 수 N에 도달할 때까지 계속한다.

---------------------------------------------------------------------------------------------

다음의 예는 N이 15인 경우다.

∙ 1부터 시작한다
∙ 1을 1+1해서 2로 바꾼다. 지금까지 비용은 1이다. (1=1*1)
∙ 2을 2+1해서 3으로 바꾼다. 지금까지 비용은 1+2이다. (2=1*2)
∙ 3을 3+3해서 6으로 바꾼다. 지금까지 비용은 1+2+1이다. (3=3*1)
∙ 6을 6+6해서 12로 바꾼다. 지금까지 비용은 1+2+1+1이다. (6=6*1)
∙ 12을 12+3해서 15로 바꾼다. 지금까지 비용은 1+2+1+1+4=9이다. (12=3*4)

여기서 9는 15에 도달하는 최소비용이다.

정수 N이 주어질 때 1부터 위의 <연산과정>을 거쳐 N에 도달하는 최소비용을 계산하는 프로그램을 작성하시오.