Migrated from Lutece 2864 二维格雷码

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有一个 $n\times m$ 大小的自然数矩阵，矩阵内部元素互不相同。我们称一个矩阵是好的，当且仅当对于矩阵中的所有元素，与它四连通（指上下左右）的任一位置的数与这个位置的数的二进制表示有且仅有一位不同。我们称一个好的矩阵中最大的元素为代表元。给定 $n,m$，求所有可能的好矩阵的最小代表元的值。

Input

第一行一个正整数 $T\ (1\le T\le 10^4)$，表示数据组数。

接下来 $T$ 行，每行两个整数 $n,m\ (1\le n,m\le 10^9)$，表示矩阵大小。

Output

对于每组数据，输出一行表示最小代表元的值。

Samples

3
1 1
4 5
1 4

0
19
3

Note

当 $n=4,m=5$ 时，一个满足条件的矩阵如下：

$$\begin{bmatrix} 16 & 0 & 8 & 12 & 4\\ 17 & 1 & 9 & 13 & 5\\ 19 & 3 & 11 & 15 & 7\\ 18 & 2 & 10 & 14 & 6\\ \end{bmatrix} $$

Resources

The 20th UESTC Programming Contest Preliminary