B'A brick is a strip of size 1 x 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 x m is such a way to place several bricks inside a rectangle n x 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 x m rectangle belongs to exactly one brick. Here n is the height of the rectangle n x 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 x m ? It is guaranteed that under restrictions in the statement at least one n x m wall exists. The first line of the input contains one integer t ( 1 <= t <= 10 ,000 ), the number of test cases. The only line of each test case contains two integers n and m ( 2 <= n, ,m <= 10^4 ). For each test case, print one integer, the maximum stability of a wall of size n x m . In the 1st test case, the maximum stability of 2 is obtained by placing two horizontal bricks 1 x 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 x 2 in each of the 7 rows. '...