A. Brick Wall
constructive algorithms; greedy; implementation; math
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\).
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.