OpenKattis
popup15 hemtal 12 [converted from problem group]

Start

2015-01-17 15:00 AKST

popup15 hemtal 12 [converted from problem group]

End

2016-01-17 15:00 AKST
The end is near!
Session is over.
Not yet started.
Session is starting in -2509 days 9:32:54

Time elapsed

8760:00:00

Time remaining

0:00:00

Problem J
Tractor

Bessie the Cow has stolen Farmer John’s tractor and is running wild on the coordinate plane! She, however, is a terrible driver, and can only move according to the following rules:

  1. Each of her movements is in the same direction as either the positive $x$-axis or the positive $y$-axis.

  2. Her $n$th movement takes her $2^{n-1}$ units forward in her chosen direction. (On her first movement, $n=1$, so she moves $1$ unit.)

Farmer John’s farm is on the coordinate plane, in the shape of a rectangle with corners at $(0,0)$, $(A,0)$, $(0,B)$ and $(A,B)$. If Bessie starts at $(0,0)$, how many points inside the farm, including the boundary, could she reach?

Input

The input begins with an integer $N$ ($1 \le N\le 100$) on a line by itself, indicating the number of test cases that follow. Each of the following $N$ lines contains two space separated integers $A$ and $B$ ($1\le A, B\le 10^8$), describing the upper-right corner of Farmer John’s farm.

Output

Output $N$ lines, with the $N$th line containing the number of points that Bessie could possibly reach in the $N$th test case.

In the first test case of the sample, Bessie can reach the following six points: $(0,0)$, $(0,1)$, $(1,0)$, $(1,2)$, $(2,1)$ and $(0,3)$.

Sample Input 1 Sample Output 1
2
2 3
7 7
6
15