Problems

# 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 (1n5000).

#### Output

The required number of ones.

Time limit 1 second
Memory limit 128 MiB
Input example #1
7

Output example #1
6

Input example #17
119
Output example #17
15


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