Муміяне Безумство
Під час екскурсії в пустелю на 2011 ACM-ICPC World Finals ви натрапляєте на стародавню єгипетську гробницю. На жаль, відкрити гробницю виявилося поганою ідеєю: раптом, те, що ще кілька хвилин тому було пустелею, тепер стало пустелею, заповненою сердитими муміями (ви теж були б сердитими, якби вас раптово розбудили після кількох тисяч років мирного сну). (На щастя, після розв'язання цієї задачі, ви прокинулися цілими і неушкодженими в готельному номері у Флориді. Розлючені мумії були лише сном.)
Зіткнувшись з цією вбивчою масою божевільних мумій, ваш єдиний шанс - тікати і намагатися втекти, перш ніж вони вас спіймають. Питання в тому: скільки часу пройде, перш ніж мумія вас спіймає, припускаючи, що ні ви, ні мумії ніколи не втомлюються?
Ми моделюємо пустелю як сітку квадратів. Ви і мумії по черзі робите ходи на сітці. Ви робите перший хід. У свій хід ви можете переміститися на будь-який з восьми квадратів, що прилягають до вашого поточного місця розташування, або можете залишитися на місці. У ходи мумій кожна мумія просто переміщується на прилеглий квадрат, який наближає її до вас (виміряно за евклідовою відстанню, припускаючи, що ви і всі мумії стоїте в центрах своїх відповідних квадратів. А може, й ні?). Можливо, що дві мумії займають один і той же квадрат.
Часовий крок складається з вашого ходу, за яким слідують ходи мумій. Мумія ловить вас, якщо вона переміщується на квадрат, де ви знаходитесь, або якщо ви переміщується на квадрат, зайнятий мумією. Звісно, ви намагаєтеся уникати бути спійманим якомога довше. Через скільки часових кроків вас спіймають?
Рисунок I.1: Переслідування мумією
На рисунку показано, що може статися, якщо вас переслідують чотири мумії. Квадрат, позначений H, - це ваша початкова позиція, а квадрати, позначені M, - початкові позиції мумій. Через чотири часових кроки вас спіймає мумія, чия початкова позиція була (3, 4) відносно вашої початкової позиції.
Вхідні дані
Вхід складається з кількох тестових випадків. Кожен тестовий випадок починається з цілого числа n (0 ≤ n ≤ 10^5), що вказує кількість мумій у пустелі. Наступні n рядків кожен містить два цілі числа x і y, що вказують, що спочатку мумія знаходиться на координатах (x, y) пустелі, де x і y обмежені 10^6 в абсолютному значенні. Ваша початкова позиція - (0, 0), і жодна мумія не починає з цієї позиції.
Останній тестовий випадок слідує за рядком, що містить число -1.
Вихідні дані
Для кожного тестового випадку виведіть номер тестового випадку, за яким слідує максимальна кількість часових кроків до того, як вас спіймають (виміряно як загальна кількість ваших ходів), або слово "ніколи", якщо ви можете уникати захоплення нескінченно.
Дотримуйтесь формату зразка виводу.