택배 기사 민서

민서는 택배 기사이다. 월요일을 활기차게 맞이한 민서는 놀랄 수밖에 없었다. 코로나19 사태로 비대면 활동이 확산하면서 택배 물량이 급증했기 때문이다. 민서에게 배정된 택배는 거의 무한개에 가까웠고 이대로라면 과로사를 피할 수 없을 것이다. 민서는 건강을 위해 오늘까지만 열심히 일하고 내일부터는 택배 기사 대신 교수를 하기로 결심했다.

민서가 사는 동네는 수직선으로 표현할 수 있으며, 민서는 수직선의 원점, 즉 좌표 0에서 배달을 준비하고 있다. 각 택배에는 0번부터 차례대로 번호가 매겨져 있으며, 택배의 목적지는 수직선 위의 좌표로 표현할 수 있다. $i$번 택배의 목적지 $D_i$는 다음과 같다.

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

여기서 $\lfloor x\rfloor$는 바닥 함수로, $x$보다 크지 않은 정수 중 가장 큰 정수를 의미한다. 예를 들어, 3번 택배의 목적지 $D_3$은 다음과 같이 계산할 수 있다.

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

민서는 수직선의 원점에서 출발하여 0번 택배부터 차례대로 배달을 시작한다. 택배를 배달하려면 현재 위치에서 택배의 목적지까지 이동해야 한다. 민서는 현재 좌표에서 인접한 좌표로, 즉 현재 좌표에서 1만큼 차이 나는 좌표로 이동할 수 있으며, 이때 1초의 시간이 걸린다. 또한 민서는 항상 최단 경로로 이동한다.

민서는 온종일 쉬지도 않고 열심히 택배를 배달하고 있다. 문득 민서는 수직선 위의 특정 좌표 $x$에 처음으로 도달하는 시점이 언제인지 궁금해졌다.

좌표 $x$가 주어졌을 때, 해당 좌표에 처음으로 도달하는 시점을 구하는 프로그램을 작성하시오.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다.

이후 $T$개의 줄에 걸쳐 정수 좌표 $x$가 한 줄에 하나씩 주어진다.

각 테스트 케이스에 대한 답을 한 줄에 하나씩 출력한다.

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

입력과 출력의 양이 방대하므로 빠른 입출력을 사용할 것을 권장한다.

답이 32비트 정수 자료형의 표현 범위를 초과할 수 있음에 유의하라.