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
Input example #17
119
Output example #17
15
Example description: (1 + 1 + 1) * (1 + 1) + 1 = 7