B. Режь, чтобы выжить
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дуэлянты Муф и Фуад входят на арену, которая представляет собой сетку размером $$$n \times m$$$.

Монстр Фуада начинает в ячейке $$$(a, b)$$$, где строки нумеруются от $$$1$$$ до $$$n$$$, а столбцы от $$$1$$$ до $$$m$$$.

Муф и Фуад будут продолжать дуэль, пока не останется сетка только с одной ячейкой.

На каждом ходу:

  • Сначала Муф разрезает сетку вдоль линии строки или столбца на две части, отбрасывая часть без монстра Фуада. Обратите внимание, что сетка должна содержать как минимум две ячейки; в противном случае игра уже закончилась.
  • После этого, в тот же ход, Фуад перемещает своего монстра в любую ячейку (возможно, ту же, в которой он находился) в оставшейся сетке.
Визуализация фаз четвертого набора входных данных.

Муф хочет минимизировать количество ходов, в то время как Фуад хочет максимизировать их. Сколько ходов продлится эта эпическая дуэль, если оба будут играть оптимально?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$) — количество строк, количество столбцов, начальную строку монстра и начальный столбец монстра соответственно.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество ходов, которые продлится эта эпическая дуэль, если оба будут играть оптимально.

Пример
Входные данные
8
2 2 1 1
3 3 2 2
2 7 1 4
2 7 2 2
8 9 4 6
9 9 5 5
2 20 2 11
22 99 20 70
Выходные данные
2
4
4
3
6
8
6
10
Примечание

В первом наборе входных данных одна из возможных последовательностей дуэли выглядит следующим образом:

  • Ход 1: Муф разрезает сетку горизонтально вдоль линии между строками $$$1$$$ и $$$2$$$, удаляя нижнюю половину и оставляя сетку размером $$$1 \times 2$$$.
  • Ход 1: Монстр Фуада находится в ячейке $$$(1,1)$$$.
  • Ход 2: Муф снова разрезает сетку $$$1 \times 2$$$, удаляет один столбец и изолирует ячейку $$$(1,1)$$$.

Дуэль завершена за $$$2$$$ хода.

В четвертом случае одна из возможных последовательностей дуэли выглядит следующим образом:

  • Ход 1: Муф разрезает сетку вертикально вдоль линии между столбцами $$$2$$$ и $$$3$$$, разделяя ее на поле $$$2 \times 2$$$ и поле $$$2 \times 5$$$, затем удаляет часть $$$2 \times 5$$$.
  • Ход 1: Фуад перемещает монстра в ячейку $$$(1,1)$$$.
  • С этого момента дуэль проходит так же, как в первом наборе входных данных — еще два хода сокращают сетку с $$$2 \times 2$$$ до одной ячейки $$$1 \times 1$$$.

В общей сложности дуэль завершена за $$$3$$$ хода.

Вы можете обратиться к изображениям в условии задачи для иллюстраций четвертого набора входных данных.