1955번 - 수식 표현

문제

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

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

예를 들어 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의 개수를 출력한다.

제한

힌트

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