Problems

# The number of ones

# The number of ones

In arithmetic expression you are allowed to use the number **1**, operations of addition, multiplication and parenthesis. What is the minimum number of ones you need to obtain the positive integer **n**?

#### Input

One number **n** (**1** ≤ **n** ≤ **5000**).

#### Output

The required number of ones.

Input example #1

7

Output example #1

6

**Example description:**
(1 + 1 + 1) * (1 + 1) + 1 = 7