평평한 지구

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

지구는 아래와 같이 칸으로 나뉜 모양을 가지며 크기 $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$줄을 출력한다.