cho.shTime limit
2s
Memory limit
128 MB
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.
The first line contains P.
Print the minimum number of operations.