Маркування карти#6845

Маркування карти

1 секунда

64 мегабайти

Дуже легка

Генерація карт є складним завданням у картографії. Важливою її частиною є автоматичне маркування міст на карті: для кожного міста існує текстова мітка, яку потрібно розмістити так, щоб жодні дві мітки не накладалися. У цій задачі розглядається простий варіант задачі автоматичного маркування карти.

Вважатимемо, що кожне місто представлене точкою на площині, а його мітка обмежена квадратом зі сторонами, паралельними осям $x$ та $y$ . Мітка кожного міста повинна бути розміщена так, щоб точка міста знаходилась рівно посередині верхньої або нижньої сторони квадрата мітки. У гарному маркуванні всі квадратні мітки мають однаковий розмір, і жодні дві мітки не накладаються, хоча можуть мати спільну сторону. Рисунок 1 ілюструє приклад гарного маркування (тексти міток не показані).

Рисунок 1

Вхідні дані

Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 10$ 1 \leq t \leq 10) — кількість тестів. Кожен тест починається з рядка, що містить ціле число $m$ ( $3 \leq m \leq 100$ 3 \leq m \leq 100) — кількість міст. Далі слідують $m$ рядків, кожен з яких містить пару цілих чисел — координати $x$ та $y$ ( $- 10000 \leq x, y \leq 10000$ -10000 \leq x, y \leq 10000) міста на карті. Жодні два міста не мають однакових координат $(x, y)$ .

Вихідні дані

Для кожного тесту в окремому рядку виведіть максимальний можливий розмір мітки (ціле число), для якого існує гарне маркування для карти.

Приклади

Приклад 1