拉胡尔和蒂娜期待着在大学开始新的一年。当他们进入新教室时,他们观察到学生的座位排列成 $$$n \times m$$$ 网格。 $$$r$$$ 行、$$$c$$$ 列中的座位用 $$$(r, c)$$$ 表示,两个座位 $$$(a,b)$$$ 和 $$$(c,d)$$$ 之间的距离为 $$$|a-c| + |b-d|$$$。
作为班长,蒂娜可以使用 $$$k$$$ 桶粉色油漆。发生以下过程。
- 首先,蒂娜在教室中选择 $$$k$$$ 个座位来用粉红色颜料进行绘画。一桶油漆可以正好涂刷一个座位。
- 蒂娜在上一步中绘制了 $$$k$$$ 座位后,拉胡尔选择了他的座位。他不会选择粉红色的座位,因为他讨厌粉红色。
- 拉胡尔选择座位后,蒂娜为自己选择座位。除了拉胡尔选择的座位之外,她可以选择任何座位,无论是否涂漆。
Rahul 希望选择一个尽可能靠近 Tina 的座位。然而,由于一些复杂的关系历史,我们无法融入声明中,蒂娜希望坐得离拉胡尔尽可能远!
现在,Rahul 想知道 $$$k = 0, 1, \dots, n \cdot m - 1$$$,如果 Tina 有 $$$k$$$ 桶油漆,如果 Rahul 和 Tina 都了解彼此的意图并且都尽可能有策略地行事,那么 Rahul 可以与 Tina 坐多近?请帮助满足拉胡尔的好奇心!
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$2 \leq n \cdot m \leq 10^5$$$) — 教室座位的行数和列数。
所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出 $$$n \cdot m$$$ 有序整数 - 拉胡尔和蒂娜之间的距离,如果他们都对每个 $$$k \in [0, n \cdot m - 1]$$$ 表现最佳。
示例
输入 #1
2 4 3 1 2
输出 #1
3 3 4 4 4 4 4 4 5 5 5 5 1 1
注意
Tina 有 $$$k=3$$$ 桶油漆的第一个测试用例的一个可能的选择顺序如下。
蒂娜用粉红色油漆在 $$$(1, 2)$$$、$$$(2, 2)$$$、$$$(3, 2)$$$ 位置的座位上涂漆。 Rahul 选择 $$$(3, 1)$$$ 的座位,之后 Tina 选择 $$$(1, 3)$$$ 的座位。
因此,Tina 和 Rahul 之间的距离为 $$$|3-1| + |1-3| = 4$$$,我们可以证明这确实是给定约束下的最小可能距离。可能还有其他座位选择也会导致相同的答案。
对于第一个测试用例中的 $$$k=0$$$,Rahul 可以决定坐在 $$$(2, 2)$$$ 处,而 Tina 可以决定坐在 $$$(4, 3)$$$ 处,因此他们之间的距离为 $$$|2 - 4| + |2 - 3| = 3$$$。
下面是第一个测试用例的 $$$k=3$$$ 和 $$$k=0$$$ 用例的图示。
$$$k=3$$$ 的可能座位安排。 $$$k=0$$$ 的可能座位安排。