## 0461. The number of ones

###### Time limit : 1000 ms Memory limit : 64 mb

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.

 № Input Output 1 7 6 2 5 5

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