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?


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 3
7 7
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.9hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in