Великий Лицар#6063

Великий Лицар

1 секунда

64 мегабайти

Дуже складна

У вас є шахівниця розміром $N \times N$ N \times N. Рядки та стовпці пронумеровані від $1$ до $N$ . Кінь починає свою подорож з клітинки в рядку $R_{1}$ R_1 та стовпці $C_{1}$ C_1. Його мета — дістатися до клітинки в рядку $R_{2}$ R_2 та стовпці $C_{2}$ C_2. Ваше завдання — перемістити коня з початкової клітинки до клітинки призначення з мінімальною кількістю ходів.

Нагадаємо, що хід коня дозволяє йому переміщуватися на $2$ клітинки вздовж однієї осі та на $1$ клітинку вздовж іншої. Тобто, якщо кінь знаходиться в $(A, B)$ , він може переміститися в $(A - 2, B - 1)$ (A-2, B-1), $(A - 2, B + 1)$ (A-2, B+1), $(A + 2, B - 1)$ (A+2, B-1), $(A + 2, B + 1)$ (A+2, B+1), $(A - 1, B - 2)$ (A-1, B-2), $(A + 1, B - 2)$ (A+1, B-2), $(A - 1, B + 2)$ (A-1, B+2) або $(A + 1, B + 2)$ (A+1, B+2). Звісно, кінь не може вийти за межі дошки.

Вам дано $N$ , $R_{1}$ R_1, $C_{1}$ C_1, $R_{2}$ R_2 та $C_{2}$ C_2. Визначте мінімальну кількість ходів, необхідних для переміщення коня з $(R_{1}, C_{1})$ (R_1, C_1) до $(R_{2}, C_{2})$ (R_2, C_2).

Вхідні дані

Перша строка вхідних даних містить додатне ціле число $T$ , що вказує на кількість тестових випадків. Кожен випадок складається з одного рядка, що містить п'ять цілих чисел $N$ ( $3 \leq N \leq 1 0^{15}$ 3 \le N \le 10^{15}), $R_{1}$ R_1, $C_{1}$ C_1, $R_{2}$ R_2 та $C_{2}$ C_2, які знаходяться в межах від $1$ до $N$ включно.

Вихідні дані

Для кожного тестового випадку виведіть мінімальну кількість ходів, необхідних для переміщення коня з $(R_{1}, C_{1})$ (R_1, C_1) до $(R_{2}, C_{2})$ (R_2, C_2). Припустимо, що завжди існує розв'язок, тобто можливо перемістити коня з його початкової клітинки до клітинки призначення.

Приклади

Приклад 1