Brick Wall
Description
A brick is a strip of size $1 \times k$, placed horizontally or vertically, where $k$ can be an arbitrary number that is at least $2$ ($k \ge 2$).
A brick wall of size $n \times m$ is such a way to place several bricks inside a rectangle $n \times m$, that all bricks lie either horizontally or vertically in the cells, do not cross the border of the rectangle, and that each cell of the $n \times m$ rectangle belongs to exactly one brick. Here $n$ is the height of the rectangle $n \times m$ and $m$ is the width. Note that there can be bricks with different values of k in the same brick wall.
The wall stability is the difference between the number of horizontal bricks and the number of vertical bricks. Note that if you used $0$ horizontal bricks and $2$ vertical ones, then the stability will be $-2$, not $2$.
What is the maximal possible stability of a wall of size $n \times m$?
It is guaranteed that under restrictions in the statement at least one $n \times m$ wall exists.
The first line of the input contains one integer $t$ ($1 \le t \le 10\,000$), the number of test cases.
The only line of each test case contains two integers $n$ and $m$ ($2 \le n,\,m \le 10^4$).
For each test case, print one integer, the maximum stability of a wall of size $n \times m$.
Input
The first line of the input contains one integer $t$ ($1 \le t \le 10\,000$), the number of test cases.
The only line of each test case contains two integers $n$ and $m$ ($2 \le n,\,m \le 10^4$).
Output
For each test case, print one integer, the maximum stability of a wall of size $n \times m$.
5
2 2
7 8
16 9
3 5
10000 10000
2
28
64
6
50000000
Note
In the 1st test case, the maximum stability of $2$ is obtained by placing two horizontal bricks $1 \times 2$ one on top of the other.
In the 2nd test case, one can get the maximum stability of $28$ by placing $4$ horizontal bricks $1 \times 2$ in each of the $7$ rows.