Power Tiller

Time limit3sMemory limit256 MB

Summary

Count distinct positions reachable by steps of lengths 1, 2, 4 and so on moving only right or up inside an A by B rectangle.

Level: Medium7 of 10
Topics: Bit manipulation, Dynamic programming, Math
Solved: No attempts yet

Problem

Yeondol has taken Sesun's power tiller out onto the coordinate plane. He drives badly, so he moves only by these two rules.

Every move points either in the positive x direction or in the positive y direction.
The $n$ -th move covers exactly $2^{n-1}$ cells in the chosen direction.

The plane Yeondol drives on is the rectangle with corners $(0, 0)$ , $(A, 0)$ , $(0, B)$ and $(A, B)$ , and the boundary belongs to the rectangle. Yeondol starts at $(0, 0)$ and never makes a move that would take him outside the rectangle. He may repeat moves as many times as he likes, or make none at all.

Counting the starting point and the position after each completed move, how many distinct coordinates can Yeondol visit?

Input

The first line contains the number of test cases $T$ ( $0 \le T \le 100$ ).

Each of the next $T$ lines contains two integers $A$ and $B$ ( $1 \le A, B \le 10^8$ ) separated by a space.

Output

For each test case, print on its own line how many distinct coordinates Yeondol can visit.

Examples3

Example 1
Input
```
2
2 3
7 7
```
Expected output
```
6
15
```
Example 2
Input
```
0
```
Expected output
Example 3
Input
```
1
1 1
```
Expected output
```
3
```