Knights of the Round Table

It is the year 573 AD, and King Arthur rules all of Britain. Governing such a large country is hard work, so he is aided by the noble Knights of the Round Table. At first this body held only the greatest heroes of the realm — Sir Gawain, Sir Lancelot, Sir Galahad — but the lasting peace led the guilds to demand a seat at the table, and Arthur, ever just, agreed. The bakers, the carpenters, even the stone masons joined, and the ranks of the “knights” swelled: a much bigger table had to be ordered, and a new wing of Castle Camelot was built to hold it.

The weekly meetings are now so crowded that people on opposite sides of the table can barely hear one another. To gauge how bad the problem really is, Arthur wants to know how far apart the two farthest members sit. The seats are not spread evenly: some sit close together to discuss important matters, while others keep their distance from their neighbours (for instance, the representative of the guild of healers and the head of the guild of assassins).

Your task is to compute the maximum distance between any pair of chairs around the table. You are given a list of angles (sorted counter-clockwise) marking the chairs' positions on the circular table. The radius of the table equals the number of knights seated at it.

The first line contains the number of scenarios.

Each scenario starts with a line containing the number $n$ of chairs ($3 \le n \le 10\,000$). Then follow $n$ lines, each containing two integers $p$ and $q$ ($0 \le p < q < 10^9$), describing a chair placed at angle $2\pi p / q$. The radius of the table equals $n$.

For each scenario, print a line “Scenario #$i$:”, where $i$ is the scenario number starting at 1, followed by a line with the maximum distance between any two chairs, rounded to exactly two digits after the decimal point. Print a blank line between consecutive scenarios.