Problem Description

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.

Input Format

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 Format

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

10
1
2
7
8
9
10
11
935
101
2023

1
-1
3
-1
4
-1
4
10
7
11

Hint

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