Задачі
Маркування карти
Маркування карти
Генерація карт є досить важким завданням у картографії. Важливною її частиною є автоматичее маркування міст на карті. Для кожного міста є текстова мітка, яка повинна бути прикріплена до свого місцезнаходження таким чином, щоб ніякі дві мітки не накладались. У цій задачі розглянемо простий випадок автоматичного маркування карти.
Припустимо, що кожне місто є точкою на площині, а його мітка у вигляді тексту обмежена квадратом зі сторонами, паралельними осям \textbf{x} та \textbf{y}. Назва кожного міста повинна розміщуватись так, щоб сама точка міста знаходилась точно у середині верхньої чи нижньої границі мітки. У гарному маркуванні усі квадратні мітки мають одинаковий розмір, ніякі дві мітки не накладаються, хоча можуть спільно використовувати один край. На \textbf{Рисунку 1} зображено приклад гарного маркування (тексти міток не показано).
За цілочисельними координатами усіх точок міст на карті необхідно знайти такий найбільший можливий цілочисельний розмір мітки, для якого існує карта з гарним маркуванням.
\includegraphics{https://static.e-olymp.com/content/fb/fbc8b2537e3fe92496f4a694361d39703fe14717.jpg}
\textit{\textbf{Рисунок 1}}
\InputFile
Перший рядок містить кількість тестів \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10}). Кожен тест починається з рядка, який містить кількість міст \textbf{m} (\textbf{3} ≤ \textbf{m} ≤ \textbf{100}). Далі йде \textbf{m} рядків, кожен з яких містить пару цілих чисел: координати \textbf{x} та \textbf{y} (\textbf{-10000} ≤ \textbf{x}, \textbf{y} ≤ \textbf{10000}) міста на карті. Ніякі два міста не мають одинакових (\textbf{x}, \textbf{y}) координат.
\OutputFile
Для кожного тесту вивести у окремому рядку максимальний цілочисельний розмір мітки, для якої існує карта з гарним маркуванням.
Вхідні дані #1
1 6 1 1 2 3 3 2 4 4 10 4 2 5
Вихідні дані #1
2