AlgoLiga 2018

W ten piękny słoneczny dzień profesor Algobit zabrał swoich studentów na przechadzkę po akademickim lesie, w którym może znajdować się nawet 10 000 pięknych zielonych drzew - głównie sosny i brzozy. Wykładowca ma dziś bardzo dobry humor i postanowił, że zaliczy całej grupie ćwiczenia z programowania równoległego pod warunkiem, że studenci znajdą największy niezalesiony obszar obrośnięty zieloną trawką. Dodatkowo obszar ten musi być w kształcie kwadratu, a jego boki muszą być równoległe do płotu, który otacza owy las. Studenci żwawo zabrali się do pracy. Szybko okazało się, że możliwości jest tak dużo, że bez twoich programistycznych umiejętności się nie obejdzie. Napisz program, nim skończy się ten piękny dzień, który znajdzie długość boku największego takiego kwadratu.

Wejście

W pierwszym wierszu jedna liczba określająca liczbę zestawów danych (nie więcej niż 10).

Specyfikacja każdego zestawu testowego:

w pierwszym wierszu cztery liczby całkowite x_A, y_A, x_B, y_B określające współrzędne naprzeciwległych wierzchołków prostokąta, który wyznacza ogrodzenie akademickiego lasu. Boki tego prostokąta są równoległe do osi współrzędnych (x_A < x_B, y_A < y_B)

Następnie jedna liczba n określająca liczbę drzew mieszczących się w ogrodzeniu.

Następnie n wierszy, w każdym wierszu po dwie liczby całkowite określające współrzędne drzew. Wszystkie współrzędne mieszczą się  w przedziale [0..10⁶].

Wyjście

Dla każdego zestawu jedna liczba określająca długość boku największego kwadratu. Boki kwadratu muszą być równolegle do osi współrzędnych.

Przykład

Wejście:
1
0 0 5 6
3
1 1
5 3
3 5

Wyjście:
4

Wyjaśnienie przykładu:

Szukany kwadrat nie może wychodzić poza granice ogrodzenia. Średnica drzewa jest pomijalnie mała.