P8918 "MdOI R5" Jump

There is a person on a number line. Let their position be $x$, and initially $x=0$. In the $i$-th second, they can choose to jump left or right by $2^{i-1}$ units, that is, increase or decrease $x$ by $2^{i-1}$. Find the minimum number of seconds needed to reach $n$, meaning that at the end of some second, $x=n$. If it is impossible to ever reach $n$, output $-1$. **In this problem, each test point contains multiple test cases.**

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain an integer, representing $n$ in one test case.

Output $T$ lines. Each line contains one number, in order, representing the answer for each test case.

For $100\%$ of the data, $1\le T\le 10^3$, $1\le n\le 10^9$. $\operatorname{Subtask} 1(30\%)$: $n\le 100$. $\operatorname{Subtask} 2(40\%)$: $n=2^k$, where $k$ is a non-negative integer. $\operatorname{Subtask} 3(30\%)$: No special constraints. #### Sample Explanation 1 When $n=1$, it is enough to jump to the right in the first second. When $n=2$, it can be proven that it is impossible to ever reach $n$. Translated by ChatGPT 5