Starting with x and repeatedly multiplying by x,
we can compute x³¹ with thirty multiplications:

<!-- MATH
$x² = x \times x$
-->
x² = x x x,    
<!-- MATH
$x³ = x² \times x$
-->
x³ = x² x x,    

x⁴ = x³ x x,    
...  ,    
<!-- MATH
$x^{31} = x^{30}\times x$
-->

x³¹ = x³⁰ x x.

The operation of squaring
can appreciably shorten the sequence of multiplications.
The following is a way to compute x³¹ with eight multiplications:

x² = x x x,     x³ = x² x x,     x⁶ = x³ x x³,     x⁷ = x⁶ x x,     x¹⁴ = x⁷ x x⁷,
x¹⁵ = x¹⁴ x x,     x³⁰ = x¹⁵ x x¹⁵,     x³¹ = x³⁰ x x.

This is not the shortest sequence of multiplications to compute x³¹.
There are many ways with only seven multiplications.
The following is one of them:

<!-- MATH
$x² = x \times x$
-->
x² = x x x,    

x⁴ = x² x x²,    
<!-- MATH
$x⁸ = x⁴ \times x^4$
-->
x⁸ = x⁴ x x⁴,    

x¹⁰ = x⁸ x x²,

<!-- MATH
$x^{20} = x^{10} \times x^{10}$
-->
x²⁰ = x¹⁰ x x¹⁰,    

x³⁰ = x²⁰ x x¹⁰,    
<!-- MATH
$x^{31} = x^{30} \times x$
-->
x³¹ = x³⁰ x x.

There however is no way to compute x³¹
with fewer multiplications.
Thus this is one of the most efficient ways to compute x³¹
only by multiplications.

If division is also available, we can find a shorter sequence of operations. It is possible to compute x³¹ with six operations (five multiplications and one division):

x² = x x x,     x⁴ = x² x x²,     x⁸ = x⁴ x x⁴,     x¹⁶ = x⁸ x x⁸,     x³² = x¹⁶ x x¹⁶,     x³¹ = x³² ÷ x.

This is one of the most efficient ways to compute x³¹ if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to compute xⁿ by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence of operations should be x to a positive integer's power. In other words, x^-3, for example, should never appear.