The number of ones

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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 \leq n \leq 5000)$ .

#### Output The required number of ones.

Examples

Input #1

Answer #1

Input #17

Answer #17

Submissions 16K

Acceptance rate 36%