eolymp
bolt
Try our new interface for solving problems
Problems

The number of ones

The number of ones

Time limit 1 second
Memory limit 128 MiB

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.

Examples

Input example #1
7
Output example #1
6
Input example #17
119
Output example #17
15