A16399 | Brick Wall

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$ .