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