시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 84 24 21 29.577%

문제

연돌이는 세순이에게서 경운기를 훔쳐서 좌표평면으로 나왔다! 하지만 연돌이는 운전을 끔찍하게 못해서 다음 규칙에 의해서만 움직일 수 있다:

  1. 각 움직임은 x축 양의 방향이나 y축 양의 방향에 평행해야 한다.
  2. n번째 움직임은 선택한 방향으로 2^(n - 1) 칸만큼 움직인다.

연돌이가 있는 평면은 (0, 0), (A, 0), (0, B), (A, B)를 꼭지점으로 가지는 직사각형 모양이다. 연돌이가 (0, 0)에서 출발한다고 할 때 평면의 경계를 포함하여 연돌이가 방문할 수 있는 좌표의 종류는 몇가지인가?

입력

첫 줄에는 테스트 케이스의 수 T(0 <= T <= 100)이 입력된다. 이어지는 N줄에 걸쳐 두 정수 A, B(1 <= A, B <= 10^8)이 입력된다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 연돌이가 N번째 평면에서 도달할 수 있는 좌표의 종류를 출력한다.

첫 테스트 케이스에서 연돌이는 (0, 0), (0, 1), (1, 0), (1, 2), (2, 1), (0, 3) 여섯점에 방문가능하다.

예제 입력

2
2 3
7 7

예제 출력

6
15

힌트