决斗者 Mouf 和 Fouad 进入竞技场,这是一个 $$$n \times m$$$ 网格!
Fouad 的怪物从单元格 $$$(a, b)$$$ 开始,其中行编号为 $$$1$$$ 到 $$$n$$$,列编号为 $$$1$$$ 到 $$$m$$$。
Mouf 和 Fouad 将继续决斗,直到网格仅由一个单元格组成。
每回合:
- Mouf首先沿着行或列线将网格切割成两部分,丢弃没有Fouad怪物的部分。请注意,网格必须至少有两个单元格;否则,游戏就已经结束了。
- 之后,在同一回合中,福阿德将他的怪物移动到剩余网格内的任何单元格(可能是原来所在的单元格)。
第四个测试用例的各个阶段的可视化。 Mouf 希望最小化回合数,而 Fouad 希望最大化回合数。如果双方都发挥最佳,这场史诗般的对决会持续多少回合?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含四个整数 $$$n$$$、$$$m$$$、$$$a$$$ 和 $$$b$$$ ($$$2 \le n, m \le 10^9$$$, $$$1 \le a \le n$$$, $$$1 \le b \le m$$$) — 表示行数、列、怪物的起始行和怪物的起始列。
输出
对于每个测试用例,输出一个整数 - 如果双方都发挥最佳状态,这场史诗般的决斗将持续的回合数。
示例
输入复制
82 2 1 13 3 2 22 7 1 42 7 2 28 9 4 69 9 5 52 20 2 1122 99 20 70
输出复制
2 4 4 3 6 8 6 10
注意
在第一个测试用例中,一个可能的决斗序列如下:
- 第 1 回合:Mouf 沿着 $$$1$$$ 行和 $$$2$$$ 行之间的线水平切割网格,删除下半部分并留下 $$$1 \times 2$$$ 网格。
- 第 1 回合:Fouad 的怪物位于单元格 $$$(1,1)$$$ 处。
- 第 2 回合:Mouf 再次切割 $$$1 \times 2$$$ 网格,删除一列,并隔离单元格 $$$(1,1)$$$。
决斗在 $$$2$$$ 回合内完成。
在第四种情况下,一种可能的决斗顺序如下:
- 第 1 回合:Mouf 沿着 $$$2$$$ 和 $$$3$$$ 列之间的线垂直切割网格,将其分成 $$$2 \times 2$$$ 和 $$$2 \times 5$$$ 字段,然后删除 $$$2 \times 5$$$ 部分。
- 第1回合:福阿德将怪物移至单元格$$$(1,1)$$$。
- 从这一点开始,决斗就像第一个测试用例一样进行——另外两个回合将网格从 $$$2 \times 2$$$ 修剪到单个 $$$1 \times 1$$$ 单元格。
总共,决斗在 $$$3$$$ 回合内完成。
第四个测试用例的说明可以参考问题陈述中提到的图片。