수식 표현

수식 표현은 문자 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의 최소 개수를 출력한다.

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