22986번 - Flat Earth

문제

지구는 평평하다. 이를 굳게 믿고 있는 해성이는 지구의 끝으로 가 보려고 한다.

지구는 아래와 같이 칸으로 구분되는 모양을 가지며 크기 $N$을 가진다.

지구의 크기 $N$이 1ドル$일 때는 정사각형 모양으로 4ドル$개의 칸이 존재한다. 지구의 크기가 1ドル$ 커질 때마다 지구의 끝과 인접한 비어있는 공간에 칸이 하나씩 생겨난다.

지구의 크기 $N$이 $i$일 때 지구의 끝은 지구의 크기가 $i$가 되면서 새로 생긴 칸들을 말한다.

$N=1$일 때는 모든 칸이 지구의 끝이다.

위 그림에서 동그라미 친 곳이 $N=1,ドル $N=2,ドル $N=3$일 때의 지구의 끝이다.

해성이는 1ドル$초에 1ドル$칸씩 움직일 수 있다. 하지만 지구의 크기도 1ドル$초에 1ドル$씩 커지기 때문에 이대로는 지구의 끝에 도달할 수 없다는 사실을 깨달은 해성이는 현자인 당신에게 도움을 요청했다.

이를 불쌍히 생각한 당신은 1ドル$초에 2ドル$칸씩 움직일 수 있는 자동차를 만들어 줬다. 슬프게도 무한동력 배터리가 아직 구현되지 않은 세상이기 때문에 자동차는 $K$초 동안만 움직일 수 있다.

해성이가 출발할 때의 지구 크기 $N$과 자동차가 움직일 수 있는 시간 $K$가 주어질 때, 지구의 끝에 도달할 수 있는 출발칸의 개수를 계산하자.

입력

다음과 같이 입력이 주어진다.

• 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. (1ドル \le T \le 1,000円$)
• 2번째 줄 부터 $T$줄에 걸쳐 한 줄에 테스트 케이스가 하나씩 주어진다.
• $N$은 현재 지구의 크기다. (1ドル \leq N \leq 10^9$)
• 1ドル$초에 2ドル$칸씩 움직이는 자동차를 $K$초간 사용할 수 있다. (0ドル \le K \le 10^9$)

출력

각 테스트 케이스별로 테스트 케이스가 주어진 순서대로 지구의 끝에 도달할 수 있는 칸의 수를 한 줄에 출력하여 총 $T$줄에 걸쳐 출력한다.

제한

힌트