원탁의 기사

서기 573년, 아서 왕이 브리튼 전역을 다스리고 있다. 넓은 나라를 통치하는 일은 고되기에, 그는 고결한 원탁의 기사들의 도움을 받는다. 처음에 이 모임은 가웨인 경, 랜슬럿 경, 갈라하드 경처럼 왕국 최고의 영웅들로만 이루어졌다. 그러나 오랜 평화 속에서 길드들이 국정에 대한 발언권을 요구했고, 언제나 공정한 아서 왕은 이를 받아들였다. 제빵사 길드, 목수 길드, 석공 길드까지 합류하면서 “기사”의 수는 크게 불어났고, 더 큰 원탁을 새로 맞추고 그것을 놓기 위해 카멜롯 성에 별관까지 지어야 했다.

이제 주간 회의는 너무 붐벼서, 원탁 반대편에 앉은 사람끼리는 서로의 말을 알아듣기조차 어렵다. 문제가 얼마나 심각한지 가늠하기 위해, 아서 왕은 가장 멀리 떨어져 앉은 두 사람이 얼마나 떨어져 있는지 알고 싶어 한다. 자리는 고르게 퍼져 있지 않다. 어떤 이들은 중요한 논의를 위해 바짝 붙어 앉고, 어떤 이들은 이웃과 거리를 두려 한다(예를 들어 치유사 길드 대표와 암살자 길드 대표).

원탁에 놓인 의자들 중 임의의 두 의자 사이의 최대 거리를 구하는 프로그램을 작성하라. 의자들의 위치를 나타내는 각도 목록(반시계 방향으로 정렬됨)이 주어진다. 원탁의 반지름은 그 자리에 앉은 기사의 수와 같다.

첫 줄에는 시나리오의 수가 주어진다.

각 시나리오는 의자의 수 $n$ ($3 \le n \le 10\,000$)이 적힌 줄로 시작한다. 이어서 $n$개의 줄이 주어지며, 각 줄에는 두 정수 $p$와 $q$ ($0 \le p < q < 10^9$)가 있어 각도 $2\pi p / q$에 놓인 의자를 나타낸다. 원탁의 반지름은 $n$과 같다.

각 시나리오마다 “Scenario #$i$:” 줄을 출력한다. 여기서 $i$는 1부터 시작하는 시나리오 번호이다. 그다음 줄에 임의의 두 의자 사이의 최대 거리를 소수점 아래 정확히 두 자리로 반올림하여 출력한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 출력한다.