곱

시간 제한1초메모리 제한128 MB

요약

(a_i+1)의 곱이 n과 a_i의 곱을 곱한 값과 같아지도록 하는 양의 정수 a_1,...,a_k의 최소 개수 k를 구합니다.

문제

양의 정수 $n$ 이 주어진다. 조지는 양의 정수 $a_1, a_2, \ldots, a_k$ 를 찾는 프로그램을 만들었다. 이 수들은 각각에 1을 더하면 그 곱이 정확히 $n$ 배가 되는 성질을 가진다. 즉,

$(a_1+1)(a_2+1)\cdots(a_k+1) = n \cdot a_1 a_2 \cdots a_k$

이 성립한다. 이제 조지는 이것이 가능한 가장 작은 $k$ 의 값을 알고 싶어 한다. 조지의 새로운 문제를 해결하는 프로그램 mink를 작성하여라.

표준 입력의 첫 줄에 정수 $n$ 이 주어진다 ( $2 < n < 1000$ ).

표준 출력에 구하고자 하는 $k$ 의 값을 한 줄에 출력한다.