AlgoLiga 2018

Tym razem bez owijania w bawełnę: Jaka jest minimalna liczba ruchów potrzebnych do przesunięcia szachowego króla z pola, na którym się znajduje na pewne pole docelowe? Aby jednak to zadanie nie było zbyt proste, rozwiążmy je na planszach o różnych rozmiarach i w dwóch wariantach: tradycyjnym i heksagonalnym.

Zarówno w szachach tradycyjnych jak i w szachach heksagonalnych król może poruszać się o jedno pole w dowolnym kierunku. W obu wariantach położenie określa się podając, w której kolumnie i którym wierszu dane pole się znajduje. Tradycyjnie kolumny na szachownicy oznaczone są literami, a wiersze - liczbami (należy tu zwrócić uwagę, że na szachownicy heksagonalnej, wiersze są "załamane" w środkowej kolumnie). Dla uproszczenia, w tym zadaniu kolumny również oznaczymy liczbami. Jako rozmiar planszy przyjmijmy liczbę pól leżących na jednym z boków planszy.

Na poniższym rysunku widzimy więc klasyczną planszę do szachów o rozmiarze 8, a obok typową planszę do szachów heksagonalnych o rozmiarze 6. Na obu szachownicach, król znajduje się w siódmej kolumnie i czwartym wierszu (czyli na polu g4). Zielone kółka oznaczają pola, na które można przesunąć króla w jednym ruchu.

Napisz program, który rozwiąże opisany problem. 

Wejście

W pierwszej linii liczba testów t (1 ≤ t ≤ 10⁶).

Następnie t linii zawierających następujące dane:
typ planszy: 1 - do zwykłych szachów, 2 - do szachów heksagonalnych;
rozmiar planszy n (1 ≤ n ≤ 10⁹);
współrzędne pola początkowego k₁ (kolumna) i w₁ (wiersz);
współrzędne pola docelowego k₂ i w₂; (1 ≤ k₁,w₁,k₂,w₂ ≤ 2·10⁹);

Wyjście

Dla każdego testu w osobnej linii jedna liczba oznaczająca minimalną liczbę ruchów potrzebnych do przesunięcia króla z pola początkowego na pole końcowe. 
Jeśli współrzędne pola początkowego lub docelowego są niewłaściwe (określają pole poza planszą), należy wypisać słowo "NONSENS".

Przykład

Wejście:
6
1 8 7 4 6 5
2 6 7 4 6 6
1 3 1 1 3 2
2 4 1 1 7 3
1 1 1 2 1 1
2 6 1 2 5 11

Wyjście:
1
1
2
4
NONSENS
NONSENS