Reach Target on Number Line

A person is initially positioned at \(x = 0\) on an infinite number line. In the \(i\)-th second, the person can jump either to the left or to the right by \(2^{i-1}\) units. That is, during the \(i\)-th second, the person's position \(x\) is updated as \(x \pm 2^{i-1}\).

Your task is to determine the minimum number of seconds required so that at the end of some second the person reaches exactly \(n\) on the number line. If it is impossible to reach \(n\) (for example, when \(n\) is even and not \(0\)), output \(-1\). Note that when \(n = 0\), the answer is \(0\) as the person starts at \(0\).

Input contains multiple test cases.

Example: For \(n = 3\), the answer is \(2\) because in the first second the person can jump \(1\) unit and in the second second \(2\) units, making a total of \(1+2=3\) units.

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains a single integer \(n\) representing the target position on the number line.

outputFormat

For each test case, output a single line containing the minimum number of seconds required to reach exactly \(n\) on the number line. If it is impossible to achieve, output \(-1\).

sample

5
0
3
2
-3
-5

0
2
-1
2
3