Products

Time limit1sMemory limit128 MB

Summary

Find the minimum count k of positive integers a1..ak such that the product of (ai+1) equals n times the product of ai.

Level: Hard8 of 10
Topics: Number theory, Math, Backtracking, Brute force
Solved: No attempts yet

Problem

Let $n$ be a positive integer. George wrote a program that finds positive integers $a_1, a_2, \ldots, a_k$ whose product increases exactly $n$ times when we add 1 to each of them; that is,

$(a_1+1)(a_2+1)\cdots(a_k+1) = n \cdot a_1 a_2 \cdots a_k$

Now he wants to find the smallest value of $k$ for which this is possible. Write a program mink that solves George's new task.

Input

The first line of standard input contains the integer $n$ ( $2 < n < 1000$ ).

Output

Write the required value of $k$ on a single line of standard output.

Examples1

Example 1
Input
```
4
```
Expected output
```
2
```