시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)27011310449.057%

문제

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

지구는 아래와 같이 칸으로 구분되는 모양을 가지며 크기 $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$

$N_1$ $K_1$

$\dots$

$N_T$ $K_T$

  • 첫 줄에 테스트 케이스의 개수 $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$줄에 걸쳐 출력한다.

예제 입력 1

2
5 2
3 0

예제 출력 1

48
12

첫 번째 테스트 케이스에서 지구의 끝에 도달 가능한 칸은 아래의 그림에서 색칠된 48칸이다.

 

두 번째 테스트 케이스에서는 자동차를 움직일 수 없기 때문에 처음에 지구의 끝에 있지 않았다면 지구의 끝에 도달할 수 없다. 문제의 그림에서 볼 수 있듯이 $N=3$일 때 지구의 끝은 총 $12$칸이 존재한다.