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 integer $n~(1 \le n \le 5000)$.
#### Output
The required number of ones.
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