Expression Representation

An expression representation is an expression made only from the symbol 1, the operators +, *, !, and parentheses (, ). It is defined by the following rules.

1. 1 is an expression representation.
2. If e is an expression representation, then (e) and e! are also expression representations.
3. If e1 and e2 are expression representations, then e1+e2 and e1*e2 are also expression representations.

For example, expressions with value 18 include (1+1+1)*(1+1+1)! and (1+1+1+1)*(1+1+1)+(1+1+1)!.

Given an integer n, find the minimum number of 1 symbols needed by any expression representation whose value is n.

The first line contains an integer n.

• 1 ≤ n ≤ 10,000

Print the minimum number of 1 symbols needed to make an expression representation with value n.

18 = (1+1+1)*(1+1+1)!