Pathetic Interview II

You all know about the story of Pathetic Interview-I. Today, I am sharing a story of my close friend who recently faced an online interview with "codecademy" which is an interactive platform that teaches people how to program. Surprisingly, instead of solving a particular problem he was asked to create a problem on Greedy Algorithm for the next contest and then upload it on his own GitHub account along with the exact solution to that problem.

He used the following git commands to upload the problem:

Git global setup

• git config --global user.name "A_M"
• git config --global user.email "12345@gmail.com"

Create a new repository

• git clone https://github.com/12345/Pathetic_Interview-II.git
• cd Pathetic_Interview-II
• touch Greedy.md
• git add Greedy.md
• git commit -m "Problem tag and solution is not guaranteed"
• git push -u origin master.

The Greedy.md file contains the following statement:
Zero and One are the most famous couple in the town. Once, Zero asked One whether she can form any number from herself with the help of operations like addition, multiplication, parenthesis-"( )" as many times as possible. One being confident of her math skills, said yes! Look how I form 10 = 1+1+1+1+1+1+1+1+1+1!!! It's great and you are very talented! said Zero.
Now being a human your task is more difficult than that of One! You have to answer what is the minimum number of 1's required to obtain the integer N? You can perform any operations like, Zero said to One earlier!

Input

The input contains one and only integer N <= 30000.

Output

The required number of ones.

Sample

7

6

Explanation of the sample case:
(1 + 1 + 1) * (1 + 1) + 1 = 7.