Power Calculus

Multiplying $x$ by $x$ thirty times yields $x^{31}$:

$$x^2 = x \times x,\quad x^3 = x^2 \times x,\quad x^4 = x^3 \times x,\quad \dots,\quad x^{31} = x^{30} \times x$$

If you are allowed to square an intermediate result, you can obtain $x^{31}$ in just $8$ operations:

$$x^2 = x \times x,\quad x^3 = x^2 \times x,\quad x^6 = x^3 \times x^3,\quad x^7 = x^6 \times x,\quad x^{14} = x^7 \times x^7,\quad x^{15} = x^{14} \times x,\quad x^{30} = x^{15} \times x^{15},\quad x^{31} = x^{30} \times x$$

If you also reuse earlier results by multiplying them together, $x^{31}$ can be reached in $7$ operations:

$$x^2 = x \times x,\quad x^4 = x^2 \times x^2,\quad x^8 = x^4 \times x^4,\quad x^{10} = x^8 \times x^2,\quad x^{20} = x^{10} \times x^{10},\quad x^{30} = x^{20} \times x^{10},\quad x^{31} = x^{30} \times x$$

This is the most efficient way to obtain $x^{31}$ using multiplication only.

If division is also allowed, the number of operations can be reduced further: $x^{31}$ can be obtained with $5$ multiplications and $1$ division:

$$x^2 = x \times x,\quad x^4 = x^2 \times x^2,\quad x^8 = x^4 \times x^4,\quad x^{16} = x^8 \times x^8,\quad x^{32} = x^{16} \times x^{16},\quad x^{31} = x^{32} \div x$$

This is the most efficient way to compute $x^{31}$ when division is as fast as multiplication.

Write a program that, starting from $x$, computes the minimum number of operations needed to build $x^n$. Only the multiplication and division described above may be used. Every intermediate result must always be a positive power of $x$; that is, something like $x^{-3}$ must never appear.

The first line contains the number of test cases $T$. Each test case consists of a single line containing an integer $n$. $n$ is a positive integer less than or equal to $1000$.

For each test case, output on its own line the minimum number of multiplications and divisions needed to build $x^n$.