Problem D
Radio Receiver

You have a radio receiver and want to receive $N$ messages. Each message is transmitted at a predetermined time measured in seconds since the epoch. Also each message is transmitted from a predetermined position representing the displacement in meters from the origin (you are in 1-dimensional space). Your radio is capable of receiving any message that is transmitted no farther than $D$ meters from your current position, where $D$ is a nonnegative real number.

You can start at any position of your choice and move at the rate of at most one meter per second. The action of receiving a message itself takes no time. Your task is to find the smallest $D$ that allows you to get all messages.

Input

The first line of input gives the number of test cases, $C$. $C$ test cases follow. For each test case there will be:

• One line containing the integer $N$, the number of messages.

• $N$ lines corresponding to the $N$ messages where each of them contains 2 integers $P$ and $T$ separated by one space. $P$ is the position where the message is transmitted from and $T$ is the time when this message is transmitted (The messages will have distinct transmission times).

You may assume that $1 \leq N \leq 1\, 000$ and $0 \leq P, T \leq 10^{9}$.

Output

For each test case, output one line containing "Case #$x$: ", where $x$ is the number of the test case, followed by the minimum value $D$ that allows you to get all messages. Answers with a relative or absolute error of at most $10^{-9}$ will be considered correct.

3
3
7 2
20 3
0 11
2
6 5
6 3
4
5 3
2 1
9 4
7 2

Case #1: 6
Case #2: 0
Case #3: 2.00