题目描述

有一个监狱，可以表示为一个有 $n$ 行 $m$ 列的矩阵，因此共有 $n \cdot m$ 个牢房。每个牢房里关押着一名囚犯。我们用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的牢房。

在牢房 $(r, c)$ 里有一条秘密通道，囚犯们将利用它逃脱！不过，为了避免被抓住，他们会在夜晚行动。

夜晚来临前，每个囚犯都在自己的牢房里。当夜晚到来时，他们可以开始向相邻的牢房移动。具体来说，在一秒钟内，位于 $(i, j)$ 的囚犯可以移动到 $(i-1, j)$、$(i+1, j)$、$(i, j-1)$ 或 $(i, j+1)$，只要目标牢房仍在监狱范围内。他们也可以选择留在原地。

囚犯们想知道，若所有人都采取最优移动策略，最少需要多少秒，才能让所有囚犯都到达 $(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$ 行，每行一个答案，表示每个测试用例的结果。

说明/提示

由 ChatGPT 4.1 翻译

样例

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

18
4
6