VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004

Opis

Megabajtolandia jest nowoczesnym miastem, wybudowanym całkiem niedawno od podstaw. Co za tym idzie, projektanci z góry rozwiązali kilka problemów, nękających do dziś miasta ewoluujące w sposób naturalny. Jednym z tych problemów jest ruch uliczny. Megabajtolandia ma kształt kwadratu (o wymiarach 1.000.000x1.000.000 kilometrów), a sieć ulic ma postać kraty. Tzn. każda ulica jest równoległa do pewnych dwóch przeciwległych boków kwadratu, a jej końce znajdują się na pozostałych dwóch bokach kwadratu (uwaga! wzdłuż boków kwadratu również są ulice!). Ponadto odległość między każdą parą sąsiednich, równoległych do siebie ulic jest równa dokładnie jednemu kilometrowi. Ulice są ponumerowane zarówno w pionie jak i w poziomie, idąc od jednego boku kwadratu do drugiego, kolejnymi liczbami całkowitymi od 0 do 1.000.000. Wszystkie ulice są dwukierunkowe i na każdym skrzyżowaniu można swobodnie jechać we wszystkie strony (nie ma mostów, tuneli, zakazów skrętu, itp.). Można poruszać się tylko wzdłuż ulic, nie istnieją żadne skróty.
To wszystko sprawia, że każde skrzyżowanie można oznaczyć parą liczb całkowitych oraz, że długość najkrótszej trasy między skrzyżowaniem o współrzędnych (x1,y1) i (x2,y2) jest równa |x1-x2|+|y1-y2| kilometrów. Długość tą będziemy nazywać odległością między skrzyżowaniami.

Pewna rozwijająca się firma taksówkowa w Megabajtolandii, o wdzięcznej i oryginalnej nazwie Taxi, nie może narzekać na brak klientów. Niestety, w godzinach szczytu ma tak dużo zleceń, że nie nadąża z ich obsługą, z powodu nie najlepszego przydziału tych zleceń. Żeby pozbyć się problemu, firma Taxi wynajęła najlepszych w branży informatyków, którym zleciła napisanie programu dokonującego skomplikowanych analiz. Tobie przypadł do napisania moduł określający największą możliwą trasę do pokonania przez taksówkę przy przewozie klienta, co będzie podstawą do szacowania obciążenia każdego z kierowców. Na szczęście w godzinach szczytu ludzie podróżują tylko i wyłącznie między urzędami (w Megabajtolandii jest dużo papierkowej roboty). Urzędy są rozmieszczone przy skrzyżowaniach ulic (przy jednym skrzyżowaniu może się mieścić dowolna liczba urzędów!). Tylko do tych skrzyżowań ogranicza się zbiór miejsc, w których klienci mogą wsiadać i wysiadać do/z taksówki, więc tylko te miejsca powinieneś brać pod uwagę w swoim programie.

Zadanie

Mając podane miejsca, w których znajdują się urzędy, oblicz odległość między parą najbardziej odległych od siebie spośród nich.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu zestawu znajduje się jedna liczba całkowita N (2 ≤ N ≤ 40.000), oznaczająca liczbę urzędów w Megabajtolandii. Kolejne N wierszy zestawu składa się z par liczb całkowitych (z zakresu od 0 do 1.000.000) - są to współrzędne tych urzędów.

Specyfikacja wyjścia

Dla każdego zestawu danych należy wypisać na wyjściu, w osobnym wierszu, jedną liczbę całkowitą - odległość między parą najbardziej odległych od siebie urzędów.

Przykład

Wejście

3
2
0 0
1 1
3
1 1
1 5
1 9
3
0 0
0 5
3 3

Wyjście

2
8
6