Read problem statement in Mandarin chinese and Vietnamese.

Suzumo has a chessboard with $N$ rows and $M$ columns. In one step, he can choose two cells of the chessboard which share a common edge (that has not been cut yet) and cut this edge.

Formally, the chessboard is split into two or more pieces if it is possible to partition its cells into two non-empty subsets $S_{1}$ and $S_{2}$ ($S_{1}\cap S_{2} = \emptyset$, $|S_{1}|+|S_{2}|=NM$) such that there is no pair of cells $c_{1}, c_{2}$ ($c_{1} \in S_{1}, c_{2} \in S_{2}$) which share a common edge that has not been cut.

Suzumo does not want the board to split into two or more pieces. Compute the maximum number of steps he can perform while satisfying this condition.

------ Input ------

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $N$ and $M$.

------ Output ------

For each test case, print a single line containing one integer — the maximum possible number of steps.

------ Constraints ------
$1 ≤ T ≤ 64$
$1 ≤ N, M ≤ 8$

----- Sample Input 1 ------
4
2 4
3 3
6 8
7 5
----- Sample Output 1 ------
3
4
35
24
----- explanation 1 ------
Example case 1:

The edges cut by Suzumo in one optimal solution are marked by red lines.

见题面

见题面