{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problem statement in \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/COOK93/mandarin/CUTBOARD.pdf\"\u003eMandarin chinese\u003c/a\u003e and \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/COOK93/vietnamese/CUTBOARD.pdf\"\u003eVietnamese\u003c/a\u003e.\u003c/h3\u003e\n\nSuzumo 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.\n\nFormally, 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 \u003d \\emptyset$, $|S_1|+|S_2|\u003dNM$) 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.\n\nSuzumo 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.\n\n### Input\n\n- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. \n- The first and only line of each test case contains two space-separated integers $N$ and $M$.\n\n### Output\n\nFor each test case, print a single line containing one integer — the maximum possible number of steps.\n\n### Constraints \n- $1 \\le T \\le 64$\n- $1 \\le N, M \\le 8$"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n2 4\n3 3\n6 8\n7 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4\n35\n24\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n**Example case 1:**\n\n\u003cimg src\u003d\"CDN_BASE_URL/6766d2292bdbed1a37f59916e3c60a94?v\u003d1715020033\"\u003e\u003c/img\u003e\n\nThe edges cut by Suzumo in one optimal solution are marked by red lines."}}]}