Given N. We can make equality with K numbers (can be repeated) like this:

(a1+1)*(a2+1)*...(aK+1) = N*a1*a2*...*aK

Find the smallest possible value of K for which there are integers that satisfy above equality.

Sample 1: Input:4 Output:2 Explanation: Integers a1 = 1 and a2 = 1 are satisfying equation.

2 < n < 1000 TL: 0.1s ML: 64MB

I thought that the answer is phi(n), but that's just a guess.