CF1918A Brick Wall

一块砖是一个尺寸为 $1 \times k$ 的长条，可以水平或垂直放置，其中 $k$ 可以是任意大于等于 $2$ 的整数（$k \ge 2$）。 一个尺寸为 $n \times m$ 的砖墙，是指在一个 $n \times m$ 的矩形内放置若干块砖，使得所有砖块都完全水平或垂直地放在格子中，不跨越矩形边界，并且矩形的每一个格子恰好属于一块砖。这里 $n$ 是矩形的高度，$m$ 是宽度。注意，同一堵砖墙中可以有不同 $k$ 值的砖块。 砖墙的稳定性定义为水平砖块数量减去垂直砖块数量。注意，如果你用了 $0$ 块水平砖和 $2$ 块垂直砖，那么稳定性为 $-2$，而不是 $2$。 对于给定尺寸为 $n \times m$ 的砖墙，最大可能的稳定性是多少？ 保证在题目条件下，至少存在一种 $n \times m$ 的砖墙。

输入的第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。 每个测试用例的唯一一行包含两个整数 $n$ 和 $m$（$2 \le n,\,m \le 10^4$）。

对于每个测试用例，输出一个整数，表示尺寸为 $n \times m$ 的砖墙的最大稳定性。

在第 1 个测试用例中，通过在每一行放置两块水平 $1 \times 2$ 的砖，可以获得最大稳定性 $2$。 在第 2 个测试用例中，可以在每一行放置 $4$ 块水平 $1 \times 2$ 的砖，共 $7$ 行，从而获得最大稳定性 $28$。 由 ChatGPT 4.1 翻译