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 non-empty 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 space-separated 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.
|Tags||alei, cakewalk, chess, cook93|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.