Let n be a positive integer. George wrote a program which finds positive integers a1, a2, ..., ak, which product increases n times if we add 1 to each of them, i.d.

(a1 + 1) * (a2 + 1) * ... * (ak + 1) = n * a1a2...ak

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.

Input

Integer number n (2 < n < 1000).

Output

Print the required value of k.