경운기

시간 제한3초메모리 제한256 MB

요약

1, 2, 4와 같이 2의 거듭제곱만큼 오른쪽이나 위쪽으로만 이동해 가로 A 세로 B 직사각형 안에서 도달할 수 있는 좌표 개수를 셉니다.

난이도: 보통10점 중 7점
유형: 비트 연산, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

연돌이가 세순이의 경운기를 훔쳐 타고 좌표평면으로 나왔다. 운전이 서툰 탓에 다음 두 규칙대로만 움직인다.

한 번의 움직임은 x축 양의 방향이나 y축 양의 방향 중 하나로만 향한다.
$n$ 번째 움직임에서는 고른 방향으로 정확히 $2^{n-1}$ 칸을 간다.

연돌이가 다니는 평면은 $(0, 0)$ , $(A, 0)$ , $(0, B)$ , $(A, B)$ 를 꼭짓점으로 하는 직사각형이고 경계도 평면에 속한다. 연돌이는 $(0, 0)$ 에서 출발하며, 직사각형을 벗어나는 움직임은 하지 않는다. 움직임은 원하는 만큼 반복해도 되고 아예 하지 않아도 된다.

출발점과 각 움직임을 마친 위치를 모두 방문한 좌표로 셀 때, 연돌이가 방문할 수 있는 좌표는 몇 가지인가?

입력

첫 줄에 테스트 케이스의 수 $T$ ( $0 \le T \le 100$ )가 주어진다.

이어지는 $T$ 개의 줄에 각각 두 정수 $A$ , $B$ ( $1 \le A, B \le 10^8$ )가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 연돌이가 방문할 수 있는 좌표의 가짓수를 한 줄에 하나씩 출력한다.

예제3

예제 1
입력
```
2
2 3
7 7
```
예상 출력
```
6
15
```
예제 2
입력
```
0
```
예상 출력
예제 3
입력
```
1
1 1
```
예상 출력
```
3
```