有一个监狱,可以表示为具有 $$$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