Products#8581

Products

1 second

128 megabytes

Medium

Let $n$ be a positive integer. George wrote a program which finds positive integers $a_{1}$ a_1, $a_{2}$ a_2, ..., $a_{k}$ a_k, whose product increases $n$ times if we add $1$ to each of them, i.e.

$(a_{1} + 1) \cdot (a_{2} + 1) \cdot ... \cdot (a_{k} + 1) = n \cdot a_{1} \cdot a_{2} \cdot ... \cdot a_{k}$ (a_1 + 1) \cdot (a_2 + 1) \cdot ... \cdot (a_k + 1) = n \cdot a_1 \cdot a_2 \cdot ... \cdot 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 George's new task.

Input

Integer number $n$ ( $2 < n < 1000$ 2 < n < 1000).

Output

Print the required value of $k$ .

Examples

Example 1

Loading

a_{1}

a_{2}

a_{k}

(a_{1} + 1) \cdot (a_{2} + 1) \cdot ... \cdot (a_{k} + 1) = n \cdot a_{1} \cdot a_{2} \cdot ... \cdot a_{k}

2 < n < 1000