3764번 - Products 다국어

문제

Let n be a positive integer. George wrote a program which finds positive integers a₁, a₂, …, a_k, which product increases n times if we add 1 to each of them, i.d.

(a₁+1)(a₂+1)...(a_k+1) = na₁a₂...a_k.

Now, however, he wants to find out what’s the smallest value of k, for which this is possible. Write a program mink, which solves the George’s new task.

입력

From the first line of the standard input it is given n (2 < n < 1000).

출력

On a line of the standard output the program must write the searched value of k.

제한

힌트