Prison Break

题意翻译

有一个 $n$ 行 $m$ 列的监狱，它的每个格子里都有一个囚犯。这些囚犯被命令走到第 $r$ 行第 $c$ 个格子。 请求出这些囚犯走到第 $r$ 行第 $c$ 个格子所需步数中的最大值。（每个囚犯每步只能往上、下、左或右四个方向走一格。） **本题每个测试点中有多组数据，具体输入格式请参见样例。** Translated By @NSObject

题目描述

There is a prison that can be represented as a rectangular matrix with $ n $ rows and $ m $ columns. Therefore, there are $ n \cdot m $ prison cells. There are also $ n \cdot m $ prisoners, one in each prison cell. Let's denote the cell in the $ i $ -th row and the $ j $ -th column as $ (i, j) $ . There's a secret tunnel in the cell $ (r, c) $ , that the prisoners will use to escape! However, to avoid the risk of getting caught, they will escape at night. Before the night, every prisoner is in his own cell. When night comes, they can start moving to adjacent cells. Formally, in one second, a prisoner located in cell $ (i, j) $ can move to cells $ ( i - 1 , j ) $ , $ ( i + 1 , j ) $ , $ ( i , j - 1 ) $ , or $ ( i , j + 1 ) $ , as long as the target cell is inside the prison. They can also choose to stay in cell $ (i, j) $ . The prisoners want to know the minimum number of seconds needed so that every prisoner can arrive to cell $ ( r , c ) $ if they move optimally. Note that there can be any number of prisoners in the same cell at the same time.

输入输出格式

输入格式

The first line contains an integer $ t $ $ (1 \le t \le 10^4) $ , the number of test cases. Each of the next $ t $ lines contains four space-separated integers $ n $ , $ m $ , $ r $ , $ c $ ( $ 1 \le r \le n \le 10^9 $ , $ 1 \le c \le m \le 10^9 $ ).

输出格式

Print $ t $ lines, the answers for each test case.

输入输出样例

输入样例 #1

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

输出样例 #1

18
4
6