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

Ремилия пытается сбежать, а Рейму хочет нанести последний удар.

Игровое поле состоит из $$$n$$$ позиций, расположенных по кругу. Для каждого $$$1 \le i \lt n$$$ позиции $$$i$$$ и $$$i+1$$$ соседние, а также позиции $$$1$$$ и $$$n$$$ тоже соседние.

Изначально, в момент времени $$$0$$$, Рейму находится на позиции $$$x_1$$$, а Ремилия  — на позиции $$$x_2$$$, где $$$x_1 \ne x_2$$$.

Каждую секунду происходит следующее в указанном порядке:

  1. Ремилия либо переходит на соседнюю позицию, либо остаётся на месте. За всю игру она может перейти на соседнюю позицию не более чем $$$k$$$ раз.
  2. После того как действие Ремилии становится известно, Рейму либо переходит на соседнюю позицию, либо остаётся на месте.
  3. Если после действий обеих игроков они оказываются на одной и той же позиции, Рейму ловит Ремилию, и игра заканчивается.

Предполагая, что оба игрока играют оптимально, Рейму всегда старается минимизировать время поимки, а Ремилия — максимизировать его.

Найдите количество секунд до того, как Рейму поймает Ремилию.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора входных данных содержатся четыре целых числа $$$n$$$, $$$x_1$$$, $$$x_2$$$ и $$$k$$$ ($$$2\le n\le10^8$$$, $$$1\le x_1,x_2\le n$$$, $$$x_1\ne x_2$$$, $$$0\le k\le 10^8$$$).

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

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

Пример
Входные данные
4
2 1 2 0
4 3 2 1
4 2 3 1
16 8 4 2
Выходные данные
1
2
2
6
Примечание

В первом наборе входных данных возможна такая последовательность действий:

  • В первую секунду Ремилия остаётся на месте, а затем Рейму переходит на $$$2$$$ и ловит Ремилию.

Во втором наборе входных данных возможна такая последовательность действий:

  • В первую секунду Ремилия переходит на $$$1$$$, а затем Рейму переходит на $$$2$$$.
  • Во вторую секунду Ремилия не может двигаться и вынуждена остаться на месте, а затем Рейму переходит на $$$1$$$ и ловит Ремилию.