← 返回题目列表

Codeforces · 1918/A

A. 砖墙

中文机器翻译题面 查看原题

砖块是尺寸为 $$$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$$$ 的最大稳定性。