Delivery Driver Minseo

Minseo is a delivery driver. She greeted Monday in high spirits, but she could not help being startled. As the COVID-19 pandemic spread remote activities, the volume of deliveries surged. The deliveries assigned to Minseo numbered nearly infinity, and at this rate she would not escape death from overwork. For her health, Minseo decided to work hard only through today and, starting tomorrow, to become a professor instead of a delivery driver.

The neighborhood where Minseo lives can be represented as a number line, and Minseo is preparing to deliver from the origin of the number line, that is, from coordinate 0. Each delivery is numbered in order starting from 0, and the destination of a delivery can be represented as a coordinate on the number line. The destination $D_i$ of delivery $i$ is as follows.

$D_i=(-1)^i\times 2^{\left\lfloor\frac{i}{2}\right\rfloor}$

Here $\lfloor x\rfloor$ is the floor function, meaning the largest integer not greater than $x$. For example, the destination $D_3$ of delivery 3 can be computed as follows.

$D_3=(-1)^3\times 2^{\left\lfloor\frac{3}{2}\right\rfloor}=-2$

Minseo starts from the origin of the number line and delivers starting from delivery 0 in order. To deliver a package, she must move from her current position to the destination of the package. Minseo can move from her current coordinate to an adjacent coordinate, that is, to a coordinate differing by 1 from her current coordinate, and this takes 1 second. Minseo also always moves along a shortest path.

Minseo delivers packages all day long without rest. It occurs to her to wonder when she first reaches a particular coordinate $x$ on the number line.

Given a coordinate $x$, write a program to find the time at which she first reaches that coordinate.

The first line gives the number of test cases $T$.

The following $T$ lines each give an integer coordinate $x$, one per line.

For each test case, output the answer on its own line.

• $1 \le T \le 100,000$
• $-1,000,000,000 \le x \le 1,000,000,000$

The volume of input and output is large, so using fast input and output is recommended.

Note that the answer can exceed the range representable by a 32-bit integer type.