시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB4561168622.165%

문제

수식 표현이란 1, +, *, !, (, )로만 이루어진 수식을 말한다. 간명하게 정의하기 위해, 다음과 같이 귀납적으로 정의할 수 있다.

  1. 1은 수식표현이다.
  2. e가 수식표현이면 (e)와 e!도 수식표현이다.
  3. e1과 e2가 수식표현이면 e1+e2와 e1*e2도 수식표현이다.

예를 들어 18의 수식표현은 (1+1+1)*(1+1+1)!, (1+1+1+1)*(1+1+1) +(1+1+1)! 등이 있다. 우리는 n이 주어졌을 때, n의 값을 갖는 수식표현을 구하고 싶다. 단, 1의 개수를 최소로 사용하는 것이어야 한다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 10,000)

출력

첫째 줄에 n의 수식표현에 필요한 최소 1의 개수를 출력한다.

예제 입력 1

18

예제 출력 1

6

힌트

18 = (1+1+1)*(1+1+1)!