The More Cats, the Better

Interview

Time limit1sMemory limit1024 MB

Summary

Given N, find the fewest creation or cloning spells that leave exactly N cats, where a cloning spell adds up to the current cat count.

Level: Medium5 of 10
Topics: Dynamic programming, Recursion, Math
Solved: No attempts yet

Problem

Magical girl Madoka loves cats so much that she has decided to raise $N$ cats at home using magic!

In each action, Madoka chooses one of the following $2$ spells and casts it. At the start, Madoka's house has no cats.

Creation spell: Creates $1$ cat in Madoka's house.
Cloning spell: Clones some or all of the cats in Madoka's house. That is, if there are currently $k$ cats in the house, Madoka can add between $0$ and $k$ cats to the house.

Madoka wants to use the $2$ spells above wisely so that the house has exactly $N$ cats in the minimum number of actions. Since Madoka finds calculating difficult, compute the minimum number of actions for her!

Input

The first line contains the desired number of cats $N$ ( $0\leq N\leq 10^{12}$ ) as an integer.

Output

On the first line, print the minimum number of actions needed to have exactly $N$ cats in Madoka's house.

Examples3

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
6
```
Expected output
```
4
```
Example 3
Input
```
2147483648
```
Expected output
```
32
```