Лицарі Круглого Столу
Це рік 573 нашої ери. Король Артур править усією Британією. Він справедливий правитель, якого любить народ. Але керувати такою великою країною — це складне завдання, яке вимагає багато зусиль. На щастя, у цьому йому допомагають найшляхетніші Лицарі Круглого Столу. Спочатку цей орган складався лише з найвідважніших героїв, яких можна було знайти в усьому королівстві, таких як сер Гавейн, сер Ланселот або сер Галахад. Однак нещодавно король Артур вважав політично необхідним прийняти додаткових членів до цього найсвятішого кола. Основною причиною цього є те, що через тривалий мир під його правлінням гільдії вимагали більшого впливу на управління країною. "Зрештою, у часи миру вам потрібен хліб більше, ніж мечі, чи не так?", сказав голова гільдії пекарів. Будучи винятково справедливим і шляхетним правителем, Артур погодився.
Це призвело до певного збільшення кількості "лицарів" круглого столу. Артур виявив, що йому довелося замовити набагато більший стіл у гільдії столярів (які, у свою чергу, негайно вимагали кілька місць за ним), і згодом довелося додати нове крило до замку Камелот, щоб його вмістити (ви можете здогадатися, що попросили каменярі після цього).
У результаті щотижневі засідання Круглого Столу тепер досить переповнені. Насправді, людей так багато, що може бути досить важко зрозуміти один одного, сидячи на протилежних сторонах столу. Щоб дізнатися, наскільки велика проблема насправді, Артур хоче, щоб ви обчислили, наскільки далеко сидять один від одного два найдальші члени Круглого Столу. Ситуація ускладнюється тим, що за столом сидить лише кінцева кількість людей, і вони не розподілені рівномірно навколо столу — деякі з них сидять близько один до одного (щоб обговорити важливі питання), тоді як інші вважають за краще триматися подалі від своїх сусідів (наприклад, представник гільдії цілителів і голова гільдії вбивць).
Ваше завдання — написати програму, яка обчислює максимальну відстань між будь-якою парою стільців навколо столу. Для цього вам надано список кутів (відсортованих проти годинникової стрілки), які вказують розташування стільців навколо столу. Радіус самого столу дорівнює кількості лицарів, які сидять за ним.
Вхідні дані
Перша рядок містить кількість сценаріїв. Кожен сценарій починається з рядка, що містить число n стільців (3 ≤ n ≤ 10000). Після цього йдуть n рядків, кожен з яких складається з двох цілих чисел p і q (0 ≤ p < q < 10^9), що позначають кут 2p/q.
Вихідні дані
Вихід для кожного сценарію починається з рядка, що містить "Сценарій #i:", де i — номер сценарію, починаючи з 1. Потім виведіть максимальну відстань, округлену до двох знаків після коми. Завершіть вихід для сценарію порожнім рядком.