Minimum Power Operations

Time limit2sMemory limit128 MB

Summary

Given P up to 20000, find the minimum number of multiply or divide operations using only two variables to reach x^P from x and 1.

Level: Hard8 of 10
Topics: BFS, Dynamic programming, Math
Solved: No attempts yet

Problem

We want to compute x^P using as few operations as possible, where 1 <= P <= 20,000. During the computation, only two variables may be used.

Initially, one variable stores x and the other stores 1. In one operation, choose two values currently stored in the variables, multiply them or divide one by the other, and store the result in either variable. The same variable may be chosen twice, so squaring a stored value is allowed. The final result may be stored in either variable.

For example, x^9 can be computed in 4 operations as follows.

Number of operations	0	1	2	3	4
Variable 1	`x`	`x`	`x`	`x^5`	`x^9`
Variable 2	`1`	`x^2`	`x^4`	`x^4`	`x^4`

Given P, find the minimum number of operations required to compute x^P.

Input

The first line contains P.

Output

Print the minimum number of operations.

Examples1

Example 1
Input
```
31
```
Expected output
```
6
```