你正在 $$$n \times m$$$ 网格上玩游戏,其中计算机选择了网格中的某个单元格 $$$(x, y)$$$,你必须确定是哪一个。
为此,您将选择一些 $$$k$$$ 和一些 $$$k$$$ 单元格 $$$(x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k)$$$,并将它们提供给计算机。作为响应,您将得到 $$$k$$$ 数字 $$$b_1,\, b_2, \ldots b_k$$$,其中 $$$b_i$$$ 是从 $$$(x_i, y_i)$$$ 到隐藏单元 $$$(x, y)$$$ 的曼哈顿距离(这样您就知道哪个距离对应于 $$$k$$$ 输入单元中的哪个)。
收到这些$$$b_1,\, b_2, \ldots, b_k$$$后,你必须能够确定隐藏单元。无论计算机选择什么单元,都可以正确猜测隐藏单元的最小 $$$k$$$ 是多少?
提醒一下,单元格 $$$(a_1, b_1)$$$ 和 $$$(a_2, b_2)$$$ 之间的曼哈顿距离等于 $$$|a_1-a_2|+|b_1-b_2|$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的单行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^9$$$) - 网格中的行数和列数。
输出
对于每个测试用例,打印一个整数 - 该测试用例的最小 $$$k$$$。
示例
输入 #1
2 2 3 3 1
输出 #1
2 1
注意
在第一个测试用例中,最小的 $$$k$$$ 是 $$$2$$$,您可以选择单元格 $$$(1, 1)$$$ 和 $$$(2, 1)$$$。
请注意,对于 $$$k = 2$$$,您无法选择单元格 $$$(1, 1)$$$ 和 $$$(2, 3)$$$,因为单元格 $$$(1, 2)$$$ 和 $$$(2, 1)$$$ 都会给出 $$$b_1 = 1, b_2 = 2$$$,因此我们无法确定哪个单元格如果计算机选择其中之一,则隐藏。
在第二个测试用例中,您应该选择 $$$k = 1$$$,为此您可以选择单元格 $$$(3, 1)$$$ 或 $$$(1, 1)$$$。