题目描述

一块砖是一个尺寸为 $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 翻译

样例

5
2 2
7 8
16 9
3 5
10000 10000

2
28
64
6
50000000