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

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.