该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

砖块是尺寸为 $1 \times k$ 的条状，水平或垂直放置，其中 $k$ 可以是至少为 $2$ ( $k \ge 2$ ) 的任意数字。

尺寸为 $n \times m$ 的砖墙是一种将多块砖块放置在矩形 $n \times m$ 内的方法，所有砖块都水平或垂直放置在单元格中，不跨越矩形的边界，并且该矩形的每个单元格恰好属于一块砖。这里， $n$ 是矩形 $n \times m$ 的高度， $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$ 的墙的最大稳定性。

5
2 2
7 8
16 9
3 5
10000 10000

2
28
64
6
50000000

样例解释

在第一个测试用例中， $2$ 的最大稳定性是通过将两个水平砖块 $1 \times 2$ 一个叠放在另一个之上来获得的。

在第二个测试用例中，通过在每一行 $7$ 中放置 $4$ 个水平砖 $1 \times 2$ 可以获得 $28$ 的最大稳定性。