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

Output

The required number of ones.

Time limit 1 second
Memory limit 64 MiB
Input example
7
Output example
6

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