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:
Each of her movements is in the same direction as either the positive $x$-axis or the positive $y$-axis.
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?
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 $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 |