Sparing w Programowaniu Politechnika Poznańska, 24.02.2007

Opis

Piotr chce zbudować ogrodzenie wokół wszystkich swoich drzew, a szczęśliwym trafem jego przyjaciel Filip ma firmę stawiającą ogrodzenia.

Będąc dobrym przyjacielem, Filip podjął się wybudowania ogrodzenia za darmo, pod warunkiem utrzymania kosztów pod kontrolą. Właściwie to zgodził się na wybudowanie ogrodzeń dla 3 kwadratowych obszarów o bokach prostopadłych do osi, pod warunkiem, że długość boku największego z nich jest możliwie najmniejsza.

Każdy obszar musi być kwadratem (czyli mieć równe boki) i musi zawierać drzewa, które są wyróżnionymi punktami na płaszczyźnie. Obszary mogą się przecinać, mogą mieć pokrywające się krawędzie, mogą mieć nawet bok o długości 0. Drzewo, które znajduje się w miejscu, gdzie przebiega siatka, również należy do ogrodzonego obszaru.

Może zajść sytuacja, że obszar zawiera tylko jedno drzewo, w tej sytuacji bok ogrodzenia wynosi 0. Na przykład poniższy rysunek pokazuje jak 3 obszary o długościach boków 0, 1 i 2 mogą zostać wykorzystane do ogrodzenia sześciu drzew.

Twoim zadaniem jest wyznaczenie minimalnego boku z największego obszaruów, które musi zbudować Filip. Na powyższym przykładzie minimalną wielkością takiego boku jest 2.

Specyfikacja wejścia

W pierwszej linii wejścia podana będzie liczba d (1 ≤ d ≤ 50) określająca liczbę scenariuszy.

Każdy scenariusz składa się z kilku linii. Pierwsza zawiera liczbę drzew n (1 ≤ n ≤ 10³). Po pierwszej linii nastąpi n kolejnych linii określających współrzędne każdego drzewa, w kolejności x potem y (0 ≤ x, y ≤ 10⁶).

Specyfikacja wyjścia

Wyjście będzie sekwencją linii, po jednej dla każdego scenariusza. Każda linia będzie zawierała długość najdłuższego obszaru zdefiniowaną w problemie.

Przykład

4
6 
2 1 
4 3 
1 0 
4 4 
3 2 
6 0 
5 
3 2 
6 0 
5 4 
1 0 
2 1 
1 
1 1 
2 
5 5 
1 0 

2
2
0
0