B. Поймать Кругу
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Доран и Круга играют в игру на сетке, состоящей из $$$(n + 1) \times (n + 1)$$$ ячеек, координаты которых представляют собой пары целых чисел от $$$0$$$ до $$$n$$$ включительно. Цель Круги — не быть пойманной Дораном как можно дольше, в то время как цель Дорана — поймать Кругу как можно раньше. Мы говорим, что Доран поймал Кругу, если они находятся в одной и той же ячейке сетки.

Чтобы сыграть в игру, Круга и Доран поочередно делают ходы, начиная с Круги:

  • Круга может либо остаться в той же ячейке, либо переместиться в ячейку, смежную вертикально или горизонтально (но не по диагонали). Формально, если Круга в данный момент находится в ячейке $$$(a, b)$$$, она может остаться в $$$(a, b)$$$ или переместиться в $$$(a-1, b), (a, b-1), (a, b+1), (a+1, b)$$$.
  • Доран может либо остаться в той же ячейке, либо переместиться в ячейку, смежную горизонтально, вертикально или по диагонали. Формально, если Доран в данный момент находится в ячейке $$$(c, d)$$$, он может остаться в $$$(c, d)$$$ или переместиться в $$$(c-1, d-1), (c-1, d), (c-1, d+1), (c, d-1), (c, d+1), (c+1, d-1), (c+1, d), (c+1, d+1)$$$.
  • Оба игрока не могут выходить за пределы сетки.
На картинке показаны возможные движения Круги и Дорана. Буквы 'K' и 'D' обозначают текущее положение Круги и Дорана, а цветные ячейки обозначают возможные позиции, в которые каждый игрок может переместиться в свой ход.

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

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

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

Каждый набор входных данных описывается одной строкой, содержащей пять целых чисел $$$n$$$, $$$r_K$$$, $$$c_K$$$, $$$r_D$$$ и $$$c_D$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le r_K, c_K, r_D, c_D \le n$$$, $$$(r_K, c_K) \ne (r_D, c_D)$$$) — $$$n$$$ это размер сетки, $$$(r_K, c_K)$$$ обозначает начальную ячейку Круги, а $$$(r_D, c_D)$$$ обозначает начальную ячейку Дорана.

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

Для каждого набора входных данных выведите время выживания Круги, если оба игрока играют оптимально. Если Круга может выживать бесконечно, выведите $$$-1$$$.

Пример
Входные данные
7
2 0 0 1 1
3 1 1 0 1
1 1 0 0 1
6 1 3 3 2
9 4 1 4 2
82 64 2 63 2
1000000000 500000000 500000000 1000000000 0
Выходные данные
1
3
1
4
2
19
1000000000
Примечание

Объяснение первого набора входных данных:

Круга начинает в $$$(0,0)$$$, а Доран начинает в $$$(1,1)$$$. В свой ход Круга может переместиться только в $$$(0,0)$$$, $$$(0,1)$$$ или $$$(1,0)$$$.

Доран, начиная с $$$(1,1)$$$, может достичь любой ячейки сетки $$$3 \times 3$$$ за один ход. Поэтому, независимо от того, куда переместится Круга, Доран всегда сможет переместиться в её ячейку в свой первый ход. Время выживания Круги составляет $$$1$$$.

Объяснение второго набора входных данных:

Круга начинает в $$$(1,1)$$$, а Доран — в $$$(0,1)$$$. Чтобы выжить в первый ход Дорана, Круга должна переместиться в ячейку, которую Доран не может достичь. Единственная такая ячейка — $$$(2,1)$$$.

После того как Круга переместится в $$$(2,1)$$$, Доран переместится в $$$(1,1)$$$, чтобы приблизиться.

Теперь, для своего второго хода, Круга снова должна переместиться в ячейку, которую Доран не может достичь, а именно в $$$(3,1)$$$. Затем Доран переместится в $$$(2,1)$$$.

Далее, независимо от того, куда Круга переместится на своём третьем ходе, Доран всегда сможет достичь её ячейки. Можно показать, что это оптимальная стратегия для обоих, и поэтому время выживания Круги составляет $$$3$$$.