Cut the Board

All submissions for this problem are available.
Read problem statement in Mandarin chinese and Vietnamese.
Suzumo has a chessboard with $N$ rows and $M$ columns. In one step, he can choose two cells of the chessboard which share a common edge (that has not been cut yet) and cut this edge. Formally, the chessboard is *split* into two or more pieces if it is possible to partition its cells into two nonempty subsets $S_1$ and $S_2$ ($S_1\cap S_2 = \emptyset$, $S_1+S_2=NM$) such that there is no pair of cells $c_1, c_2$ ($c_1 \in S_1, c_2 \in S_2$) which share a common edge that has not been cut. Suzumo does not want the board to split into two or more pieces. Compute the maximum number of steps he can perform while satisfying this condition. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first and only line of each test case contains two spaceseparated integers $N$ and $M$. ### Output For each test case, print a single line containing one integer — the maximum possible number of steps. ### Constraints  $1 \le T \le 64$  $1 \le N, M \le 8$ ### Example Input ``` 4 2 4 3 3 6 8 7 5 ``` ### Example Output ``` 3 4 35 24 ``` ### Explanation **Example case 1:** The edges cut by Suzumo in one optimal solution are marked by red lines.Author:  alei 
Editorial  https://discuss.codechef.com/problems/CUTBOARD 
Tags  alei, cakewalk, chess, cook93 
Date Added:  15042018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions