Products

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.

Input

Integer number n (2 < n < 1000).

Output

Print the required value of k.

Examples