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).

Problem

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 ≤ l ≤ 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.

Sample Input

1
4
0 1
1 4
2 3
4 5

Sample Output

Scenario #1:
7.90