← 返回题目列表

Codeforces · 1415/A

A. 越狱

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

有一个监狱,可以表示为具有 $$$n$$$ 行和 $$$m$$$ 列的矩形矩阵。因此,监狱牢房有 $$$n \cdot m$$$ 间。还有 $$$n \cdot m$$$ 囚犯,每间牢房一名。我们将第 $$$i$$$ 行和第 $$$j$$$ 列中的单元格表示为 $$$(i, j)$$$。

牢房里有一条秘密隧道$$$(r, c)$$$,囚犯们可以用它逃跑!不过,为了避免被抓的风险,他们会在夜间逃跑。

入夜前,每个囚犯都在自己的牢房里。当夜幕降临时,它们可以开始移动到相邻的牢房。正式来说,在一秒钟内,位于牢房 $$$(i, j)$$$ 中的囚犯可以移动到牢房 $$$( i - 1 , j )$$$ 、 $$$( i + 1 , j )$$$ 、 $$$( i , j - 1 )$$$ 或 $$$( i , j + 1 )$$$ ,只要目标牢房位于监狱内。他们还可以选择留在牢房$$$(i, j)$$$。

囚犯们想知道每个囚犯以最佳移动方式到达牢房 $$$( r , c )$$$ 所需的最少秒数。请注意,同一牢房内可以同时有任意数量的囚犯。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$,测试用例的数量。

接下来的 $$$t$$$ 行包含四个空格分隔的整数 $$$n$$$、$$$m$$$、$$$r$$$、$$$c$$$ ($$$1 \le r \le n \le 10^9$$$、$$$1 \le c \le m \le 10^9$$$)。

输出

打印 $$$t$$$ 行,每个测试用例的答案。

示例

输入 #1

3
10 10 1 1
3 5 2 4
10 2 5 1

输出 #1

18
4
6