Великий Лицар
У вас є шахівниця розміром N×N. Рядки та стовпці пронумеровані від 1 до N. Кінь починає свою подорож з клітинки в рядку R1 та стовпці C1. Його мета — дістатися до клітинки в рядку R2 та стовпці C2. Ваше завдання — перемістити коня з початкової клітинки до клітинки призначення з мінімальною кількістю ходів.
Нагадаємо, що хід коня дозволяє йому переміщуватися на 2 клітинки вздовж однієї осі та на 1 клітинку вздовж іншої. Тобто, якщо кінь знаходиться в (A, B), він може переміститися в (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). Звісно, кінь не може вийти за межі дошки.
Вам дано N, R1, C1, R2 та C2. Визначте мінімальну кількість ходів, необхідних для переміщення коня з (R1, C1) до (R2, C2).
Вхідні дані
Перша строка вхідних даних містить додатне ціле число T, що вказує на кількість тестових випадків. Кожен випадок складається з одного рядка, що містить п'ять цілих чисел N (3 ≤ N ≤ 10^15), R1, C1, R2 та C2, які знаходяться в межах від 1 до N включно.
Вихідні дані
Для кожного тестового випадку виведіть мінімальну кількість ходів, необхідних для переміщення коня з (R1, C1) до (R2, C2). Припустимо, що завжди існує розв'язок, тобто можливо перемістити коня з його початкової клітинки до клітинки призначення.