Description

It is the year 573 AD. King Arthur rules all of Britain. He is a just ruler, loved by the people. But governing such a big country is a daunting task, and doing it requires a lot of effort. Luckily, in this HE is aided by the most noble Knights of the Round Table. Initially, this body was composed only out of the most valiant heroes to be found in the whole kingdom, like Sir Gawain, Sir Lancelot, or Sir Galahad. Recently, though, King Arthur found it to be a political necessity to admit additional members to this most holy round. The main reason for this is that due to the lasting peace under his reign, the guilds demanded more influence on the ruling of the country. “After all, in times of peace you need bread more than swords, don’t you?”, said the head of the guild of bakers. Being an exceptionally just and noble ruler, Arthur agreed.

This has lead to a certain swelling of the ranks of the “knights” of the round table. Arthur found that he had to order a much bigger table from the guild of carpenters (who in turn immediately demanded some seats on it), and subsequently had to add a new wing to Castle Camelot to contain it (you may guess what the stone masons requested afterwards).

As a result, the weekly meetings of the Round Table are rather crowded now. In fact, there are so many people that it can be quite hard to understand each other when sitting at opposites sides of the table. To find out how big the problem really is, Arthur wants you to compute how far away the two farthest members of the Round Table sit from each other. Things are complicated by the fact that there is only a finite number of people sitting at the table, and they are not spread equally around the table — some of them are sitting closely together (to discuss important matters), while others prefer to distance themselves from their neighbors (e. g., the representative of the guild of healers and the head of the guild of assassins).

Your task is to write a program that computes the maximum distance between any pair of chairs around the table. To this end, you are given a list of angles (sorted counter-clockwise) that indicate the placement of the chairs around the table. The radius of the table itself is equal to the number of knights sitting at it.

Input

The first line contains the number of scenarios. Each scenario starts with a line containing the number n of chairs (3 ≤ n ≤ 10 000). After that follow n lines, each consisting of two integers p and q (0 ≤ p < q < 10⁹), denoting the angle 2πp ⁄ q .

Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print the maximal occurring distance, rounded to two digits after the decimal point. Terminate the output for the scenario with a blank line.

1
4
0 1
1 4
2 3
4 5

Scenario #1:
7.90

Source

TUD Programming Contest 2006, Darmstadt, Germany