题目背景

2023第一届粤港澳信息学创新大赛初中组复赛T2

注意：本题是以文件读写的方式进行评测，请在代码中使用freopen()等文件读写的方式进行输入输出。

文件名请参考本标题下方的“文件IO:”后面的内容

题目描述

小明是一位勇敢的探险家，他正在探索一所神秘的迷宫。迷宫的结构非常独特，呈环形排列，宛如一个迷宫的漩涡。每个房间都有一个数字表示。具体而言，下面是一个$4*5$ 大小的迷宫矩阵。

1	2	3	4	5
14	15	16	17	6
13	20	19	18	7
12	11	10	9	8

房间的编号是一个顺时针的环形排列。

小明目前身处房间$x$ ，他想知道距离他最近的目标房间$y$ 有多远。我们可以使用曼哈顿距离来计算。

曼哈顿距离就像在这个迷宫中探险，表示最少需要经过多少个房间才能从一个房间到达另一个房间。假设房间$x$ 位于第$a_1$ 行$b_1$ 列，房间$y$ 位于第$a_2$ 行 $b_2$ 列，那么这两个房间的曼哈顿距离为$|a_1 - a_2| + |b_1 - b_2|$，其中$|x|$ 表示$x$ 的绝对值。

输入格式

第一行包含一个正整数$T$，表示测试数据的组数。

接下来$T$ 行，每行是一组测试数据，包含四个正整数$n,m,x,y$， 表示迷宫的行、列以及小明所在的房间号和目标房间号。

输出格式

输出$T$ 行，每行包含一个整数，表示对应测试数据到目标房间的曼哈顿距离。

输入输出样例 #1

2
4 5 20 17
4 5 20 18

3
2

说明/提示

【样例1解释】

$4 \times 5$的迷宫如题意所示。

小明所在的房间$20$位于第$3$行第 $2$列，目标房间 $17$位于第 $2$行第$4$列，它们的曼哈顿距离为 $|3 - 2| + |2 - 4| = 1 + 2 = 3$。

【数据范围】

对于 $30\%$ 的数据，满足 $ T \leq 10, n \leq 10^5, m \leq 10^5, n\times m \leq 10^5$ 。

对于另外 $40\%$ 的数据，满足 $T \leq 5, n \leq 10^6, m \leq 10^6$ 。

对于 $100\%$ 的数据，满足 $ T \leq 10^4, n \leq 10^{18}, m \leq 10^{18}, n\times m \leq 10^{18}, x \leq 10^{18}, y \leq 10^{18}$ 。

5
746021 563676 359289577694 156029783810
625000 408420 205202369801 184405393034
496009 237691 99473818730 96818573962
426785 233021 53455139841 88373476402
331752 122314 37147954894 36998084677

698200
214215
85544
101209
41507

10
1000 100 253 9999
1000 100 28299 40600
1000 100 7783 88202
1000 100 80971 97435
1000 100 26573 2670
1000 100 30877 34922
1000 100 18858 69501
1000 100 69731 7972
1000 100 14337 28969
1000 100 56611 42060

848
119
99
150
319
111
107
319
190
305

3
1000000000 1000000000 12565632345 1000000000000000000
1000000000 1000000000 25077777890045901 319598580818361597
1000000000 1000000000 544880777556913870 517369609369563862

565632381
762152900
600308024