砖块是尺寸为 $$$1 \times k$$$ 的条带,水平或垂直放置,其中 $$$k$$$ 可以是至少 $$$2$$$ ($$$k \ge 2$$$) 的任意数字。
尺寸为 $$$n \times m$$$ 的砖墙是一种将多块砖块放置在 $$$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$$$ 的墙的最大稳定性。
示例
输入 #1
5 2 2 7 8 16 9 3 5 10000 10000
输出 #1
2 28 64 6 50000000
注意
在第一个测试用例中,通过将两块水平砖 $$$1 \times 2$$$ 一块放在另一块上面来获得 $$$2$$$ 的最大稳定性。
在第二个测试用例中,通过在 $$$7$$$ 行的每一行中放置 $$$4$$$ 水平砖 $$$1 \times 2$$$ 可以获得 $$$28$$$ 的最大稳定性。