Генерация карт является трудной задачей в картографии. Важной ее частью является автоматическая маркировка городов на карте. Для каждого города имеется текстовая метка, которая должна быть прикреплена к своему месторасположению таким образом, чтобы никакие две метки не накладывались. В этой задаче рассмотрим простой случай автоматической маркировки карты.
Предположим, что каждый город является точкой на плоскости, а его метка в виде текста ограничена квадратом со сторонами, параллельными осям x и y. Название каждого города должно располагаться так, чтобы сама точка города находилась точно в середине верхней или нижней границы метки. В хорошей маркировке все квадратные метки имеют одинаковый размер, никакие две метки не накладываются, хотя могут совместно использовать один край. На Рисунке 1 изображен пример хорошей маркировки (тексты меток не показаны).
По целочисленным координатам всех точек городов на карте необходимо найти такой наибольший возможный целочисленный размер метки, для которой существует карта с хорошей маркировкой.
Рисунок 1
Первая строка содержит количество тестов t (1 ≤ t ≤ 10). Каждый тест начинается со строки, содержащей количество городов m (3 ≤ m ≤ 100). Далее следует m строк, каждая из которых содержит пару целых чисел: координаты x и y (-10000 ≤ x, y ≤ 10000) города на карте. Никакие два города не имеют одинаковые (x, y) координаты.
Для каждого теста вывести в отдельной строке максимальный целочисленный размер метки, для которой существует карта с хорошей маркировкой.