В арифметическом выражении разрешается использовать число 1, операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число n?

Входные данные

Одно число n (1 ≤ n ≤ 5000).

Выходные данные

Искомое количество единиц.