시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB122554953.846%

문제

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

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

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

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

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

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

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

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

입력

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

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

출력

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

제한

  • 1 ≤ T ≤ 100,000
  • -1,000,000,000 ≤ x ≤ 1,000,000,000

예제 입력 1

5
0
1
2
3
4

예제 출력 1

0
1
6
15
16

힌트

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

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