Let n be a positive integer. George wrote a program which finds positive integers a[1]
, a[2]
, ..., a[k]
, which product increases n times if we add 1 to each of them, i.d.
(a[1]
+ 1) * (a[2]
+ 1) * ... * (a[k]
+ 1) = n * a[1]a[2]...a[k]
Now, however, he wants to find out what's the smallest value of k, for which this is possible. Write a program which solves the George's new task.
Integer number n (2 < n < 1000).
Print the required value of k.