Find number of ones to get a number using + and * Introduction

Your goal is to find the least number of ones you need to add or multiply together to get the input value, this is A005245.

Input

One positive integer N.

Output

The smallest number of ones that must be added/multiplied to get N.

Sample Input


  7


Sample Output


  6


Explanation


  (1 + 1 + 1) * (1 + 1) + 1 = 7
  
  Because this requires 6 ones, the output is 6


Test cases

 1  1
 2  2
 3  3
 5  5
10  7
20  9
50 12


As this is a code-golf challenge, lowest number of bytes wins.
Python 2, 74 70 bytes



f=lambda n:min([n]+[f(j)+min(n%j*n+f(n/j),f(n-j))for j in range(2,n)])


Try it online!

Alternate version, 59 bytes (unverified)

f=lambda n:min([n]+[f(j)+f(n/j)+f(n%j)for j in range(2,n)])


This works at least up to n = 1,000,000, but I have yet to prove that it works for all positive n.

Try it online!